Skip to main content
Springer Nature Link
Log in

Guessing games and distributed computations in synchronous networks

  • Parallel And Distributed Computing
  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1987)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 267))

Included in the following conference series:

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. K. Abrahamson, A. Adler, R. Gelbart, L. Higham, D. Kirkpatrick, "The bit complexity of probabilistic leader election on a unidirectional ring", Proc. 1st Int. Workshop on Distributed Algorithms on Graphs, Aug. 1985. 3–11.

    Google Scholar 

  2. D. Angluin, "Local and global properties in networks of processes", Proc. 12th ACM Symp. on Theory of Computing, April 1980, 82–93.

    Google Scholar 

  3. C. Attiya, M. Snir, M. Warmuth, "Computing on an anonymous ring", Proc. 4th ACM Symp. on Principles of Distributed Computing, Aug. 1985, 196–204.

    Google Scholar 

  4. J.L. Bentley, D.J. Brown, "A general class of resource tradeoffs", Proc. 21th Symp. on Foundations of Computer Science, Oct. 1980, 217–228.

    Google Scholar 

  5. H.L. Brolaender, J. van Leeuwen, "New upperbounds for distributed extrema-finding in a ring of processors", Proc. Int. Workshop on Distributed Algorithms on Graphs, Aug. 1985, 27–40.

    Google Scholar 

  6. J. Burns, "A formal model for message passing systems", TR-91, Indiana University, Sept. 1981.

    Google Scholar 

  7. E.J. Chang, "Echo algorithms: depth parallel operations on general graphs", IEEE Trans. Softw. Eng. SE-8, 1982, 391–400.

    Google Scholar 

  8. D. Dolev, M. Klawe, M. Rodeh, "An O(n log n) unidirectional algorithm for extrema-finding in a circle", J. Algorithms 3, 1983, 245–260.

    Google Scholar 

  9. G.N. Frederickson, N. Lynch, "The impact of synchronous communication on the problem of electing a leader in a ring", Proc. 16th ACM Symp. Theory of Computing, April 1984, 493–503.

    Google Scholar 

  10. G.N. Frederickson, N. Santoro, "Symmetry breaking in synchronous networks", Proc. 2nd Int. Workshop on Parallel Computing and VLSI, July 1986, 26–33.

    Google Scholar 

  11. E. Gafni, "Improvements in the time complexity of two message-optimal election algorithms", Proc. 4th ACM Symp. on Principles of Distributed Computing, Aug. 1985, 175–185.

    Google Scholar 

  12. R.G. Gallager, "Finding a leader in a network with O(e)+O(n log n) messages", MIT, 1979.

    Google Scholar 

  13. A. Itai, M. Rodeh, "Symmetry breaking in distributive networks", Proc. 22nd IEEE Symp. on Foundations of Computer Science, Oct. 1981, 150–158.

    Google Scholar 

  14. E. Korach, S. Moran, S. Zaks, "Tight lower and upper bounds for some distributed algorithms for a complete network of processors", Proc. 3rd ACM Symp. Princ. Distr. Comput., 1984, 199–207.

    Google Scholar 

  15. E. Korach, D. Rotem, N. Santoro, "Distributed election in a circle without a global sense of orientation", Int. J. Comput. Math. 16, 1984, 115–124.

    MathSciNet  Google Scholar 

  16. M.C. Loui, T.A. Matsushita, D.B. West, "Election in a complete network with a sense of direction", Information Processing Letters, 1986.

    Google Scholar 

  17. A. Marchetti-Spaccamela, "New protocols for the election of a leader in a ring", Proc. 5th Conf. on Foundations of Software Technology and Theoretical Computer Science, Dec. 1985.

    Google Scholar 

  18. M. Overmars, N. Santoro, "Bit vs time tradeoffs for elections in synchronous rings", CS-TR-97, Carleton University, June 1986.

    Google Scholar 

  19. J. Pachl, D. Rotem, E. Korach, "Lower bounds for distributed maximum finding algorithms", J. ACM 31, 1984, 380–401.

    Google Scholar 

  20. G.L. Peterson, "An O(n log n) unidirectional algorithm for the circular extrema problem", ACM Trans. Prog. Lang. Syst. 4, 1982, 758–762

    Google Scholar 

  21. N. Santoro, "On the message complexity of distributed problems", Int. J. Comput. Inf. Sci. 13, 1984, 131–147.

    Google Scholar 

  22. N. Santoro, D. Rotem, "On the complexity of distributed elections in synchronous graphs", Proc. 11th Int. Workshop on Graphtheoretic Concepts in Computer Science, June 1985, 337–346.

    Google Scholar 

  23. P. Vitanyi, "Distributed elections in an Archimedean ring of processors", Proc. 16th ACM Symp. Theory of Computing, April 1984, 542–547.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Utrecht, The Netherlands

    Jan van Leeuwen

  2. School of Computer Science, Carleton University, Canada

    Nicola Santoro

  3. Department of Computer Science, University of Ottawa, Ottawa, Canada

    Jorge Urrutia

  4. Department of Computer Science, Technion, Haifa, Israel

    Shmuel Zaks

Authors
  1. Jan van Leeuwen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicola Santoro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jorge Urrutia
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shmuel Zaks
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Thomas Ottmann

Rights and permissions

Reprints and permissions

Copyright information

© 1987 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

van Leeuwen, J., Santoro, N., Urrutia, J., Zaks, S. (1987). Guessing games and distributed computations in synchronous networks. In: Ottmann, T. (eds) Automata, Languages and Programming. ICALP 1987. Lecture Notes in Computer Science, vol 267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18088-5_29

Download citation

  • DOI: https://doi.org/10.1007/3-540-18088-5_29

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-18088-3

  • Online ISBN: 978-3-540-47747-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation