References

1

N. Alon, L. Babai, and A. Itai,
A fast and simple randomized parallel algorithm for
the maximal independent set problem
J. Algorithms Vol. 7, 567-583, 1986.

2

J. Aspnes and M. Herlihy, Fast Randomized Consensus using Shared Memory, J. Algorithms Vol. 11, 441-461, 1990.

3

J. Aspnes and O. Waarts, Randomized Consensus in Expected $O(N \log^2 N)$Operations per Processors, SIAM J. Comp., Vol. 25, 1024-1044, 1996.

4

H. Attiya, Lecture Notes for Distributed Algorithms, Course # 236357, Dept of CS, The Technion, January 1994.

5

B. Awerbuch,
Complexity of network synchronization,
J. ACM, Vol. 32, 804-823, 1985.

6

B. Awerbuch, private communication.

7

B. Awerbuch, A. V. Goldberg, M. Luby, and S. Plotkin, Network decomposition and locality in distributed computation, in Proc. of the 30th Annual Symposium on the Foundations of Computer Science (FOCS 89), 364-369, 1989.

8

M. Ben Or,
Another advantage of free-choice:
Completely asynchronous agreement protocols,
Proceedings of the 2nd annual ACM symposium on Principles of Distributed Computing (PODC 83) 27-30, Montreal, Canada, 1983.

9

B. Bollobás,
Graph Theory, Springer Verlag, New York, 1979.

10

J. A. Bondy and U. S. R. Murty,
Graph theory with applications, North Holland, 1976.

11

T. Chandra and S. Toueg, Unreliable Failure Detector for Reliable Distributed Systems, to appear in the J. ACM. Preliminary version in the Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, 325-340, ACM Press 1991.

12

T. Chandra, V. Hadzilacos, and S. Toueg, The weakest failure detector for solving consensus, to appear in the J. ACM. Preliminary version in the Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, 147-158, ACM Press 1992.

13

S. Chaudhuri and D. Dubhashi,
Probabilistic recurrence relations revisited,
Proc. of the 2nd Latin Amer. Symp. (LATIN 95), April 1995. LNCS 911, 207-219. To appear in Theoretical Comp. Sci.

14

R. Cole and U. Vishkin,
Deterministic coin tossing and accelerating cascades:
micro and macro techniques for designing parallel algorithms.
In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC 86), 206-219, Berkeley, California, 1986.

15

E. W. Dijkstra, Self-stabilization in spite of distributed control, Comm. ACM, Vol. 17, 643-644, 1974.

16

E. W. Dijkstra, A belated proof of self-stabilization, Distributed Computing, Vol. 1, 5-6, 1986.

17

D. Dolev, M. J. Fischer, R. Fowler, and N. A. Lynch,
An efficient algorithm for Byzantyne agreement without authentication,
Information and Control, Vol. 52, 257-274, March 1982.

18

M. Fischer, N. Lynch, and M. Paterson,
Impossibility of distributed consensus with one faulty process, J. ACM, Vol. 32, 374-382, 1985

19

R. L. Graham, B. L. Rotschild and J. H. Spencer,
Ramsey Theory, John Wiley and Sons. 1980

20

D. Karp,
Probabilistic recurrence relations,
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC 91) 190-197, New Orleans, Luisiana, 1991.

21

P. Klein, S. A. Plotkin, S. Rao, and E. Tardos,
Approximation algorithms for Steiner and sirected multicuts,
J. Algorithms, Vol. 22, 241-269, 1997.

22

D. Kozen,
The design and analysis of algorithms,
Springer Verlag, Berlin, 1992.

23

L. Lamport, R. Shostak, and M. Pease,
The byzantine generals problem,
ACM Trans on Prog Lang and Syst, Vol. 4, 382-401, 1982.

24

N. Linial,
Locality in Distributed Graph Algorithms,
SIAM J. Comput. Vol. 21, 193-201, 1992.

25

N. Linial and M. Saks,
Decomposing graphs into regions of small diameters,
Combinatorica, Vol. 13, 1993.

26

M. Luby,
A simple parallel algorithm for the maximal independent set problem
Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 85) 1-10, Providence, Rhode Island, 1985.

27

N. A. Lynch,
Distributed Algorithms,
Morgan Kaufmann, San Francisco, 1996.

28

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

29

A. Panconesi and A. Srinivasan,
On the complexity of distributed network decomposition,
J. Algorithms, Vol. 20, 356-374, 1996.

30

M. Pease, R. Shostak, and L. Lamport,
Reaching agreement in the presence of faults,
J. ACM, Vol. 27, 228-234, 1980.

31

T. K. Srikanth and S. Toueg,
Simulating authenticated bradcasts to derive simple fault-tolerant algorithms,
Distributed Computing, Vol. 2, 80-94, 1987.

32

S. Sundaram,
private communication.