Average and randomized complexity of distributed problems

1. Abrahamson K.: On Achieving Consensus Using a Shared Memory. The ACM Symposium on Principles of Distributed Computing, Toronto 1988, 291–302.

   Google Scholar 

2. Angluin D.: Local and global properties in networks of processes. 12th Annual ACM Symp. on Theory of Computing, Los Angeles, California, 82–93 (April 1980)

   Google Scholar 

3. Attia C., Snir M.: Better Computing on the Anonymous Ring. IBM RC 13657 (1988)

   Google Scholar 

4. Attia C., Snir M., Warmuth M.: Computing on the Anonymous Ring. The 4th Annual ACM Symposium on Principles of Distributed Computing (1985) 196–203

   Google Scholar 

5. Bodlaender H.L.: New Lower Bound Techniques for Distributed Leader Finding and Other Problems on Rings of Processors. Theoretical Computer Science, 81 (1991) 237–256

   Article  Google Scholar 

6. Burns J.E.: A Formal Model for Message Passing Systems. Technical Report TR-91, Indiana University, (Sept. 1980)

   Google Scholar 

7. Dolev S., Israeli A., Moran S.: Uniform Dynamic Self-Stabilizing Leader Election. WDAG Delphi, Greece, (Oct. 1991)

   Google Scholar 

8. Duris, P., Z. Galil: Two Lower Bounds in Asynchronous Distribute Computation. 28th FOCS (1987) 326–330

   Google Scholar 

9. Dolev, S., M. Klawe, M. Rodeh: An Ω(n log n) Unidirectional Distributed Algorithm for Extreme Finding in a Circle. J. Algorithms 3 (1982) 245–260

   Article  Google Scholar 

10. Fredrickson, G.N., Lynch, N.A.: Electing a Leader in a Synchronous Ring, J. ACM, 34 (1987) 98–115

    Article  Google Scholar 

11. Fich, F.E., F. Meyer auf der Heide, P. Ragde, A. Wigderson: One, Two, Three ... Infinity: Lower Bounds for Parallel Computation, 17 STOC, (1985) 48–58

    Google Scholar 

12. Gill, J.: Computational Complexity of Probabilistic Turing Machines. 6th STOC (1974) 91–95. Revised Feb. 1977.

    Google Scholar 

13. Itai, A., M. Rodeh, Probabilistic Methods for Breaking Symmetry in Distributed Networks. Information and Computation, 88 (1990) 60–87

    Article  Google Scholar 

14. Knuth, D., The Art of Computer Programming. Vol 3, Addison-Wesley (1973)

    Google Scholar 

15. Korach, E., S. Kutten, S. Moran: A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms. ASM Trans. on Programming Languages and Systems 12 (1990) 84–101

    Article  Google Scholar 

16. Pachl, J., E. Korach, D. Rotem: Lower Bounds for Distributed Maximum-finding Algorithms. J. ACM 31 (1984) 905–918

    Article  Google Scholar 

17. Pachl, J., A Lower Bound for Probabilistic Distributed Algorithms. J. Alg. 8 (1987) 53–65

    Google Scholar 

18. Peterson, G. L., An O(n log n) Unidirectional Algorithm for the Circular Extrema Problem. ACM Trans. on Prog. Languages and Systems 4 (1982) 758–762

    Article  Google Scholar 

19. Rabin, M., “Probabilistic Algorithms”, in Algorithms and Complexity. J. Traub (ed.) Academic Press (1976) 21–40

    Google Scholar 

20. Von Neumann, Zur Theorie der Gesellsschaftsspiele, Math. Annalen 100 (1974) 295–320

    Article  Google Scholar 

21. Yao, A.C.: Probabilistic Computations: Towards a Unified Measure of Complexity. 18th FOCS (1977) 222–227

    Google Scholar 

Download references