Document Open Access Logo

Singularly Optimal Randomized Leader Election

Authors Shay Kutten , William K. Moses Jr. , Gopal Pandurangan , David Peleg

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.22.pdf
  • Filesize: 0.55 MB
  • 18 pages

Document Identifiers

Author Details

Shay Kutten
  • Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel
William K. Moses Jr.
  • Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel
Gopal Pandurangan
  • Department of Computer Science, University of Houston, TX, USA
David Peleg
  • Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel

Funding

  • Kutten, Shay: This work was supported in part by the Bi-national Science Foundation (BSF) grant 2016419.
  • Moses Jr., William K.: This work was supported in part by the BSF grant 2016419 and in part by a Technion fellowship.
  • Pandurangan, Gopal: G. Pandurangan was supported, in part, by NSF grants CCF-1527867, CCF-1540512, IIS-1633720, CCF-1717075, and BSF grant 2016419.
  • Peleg, David: Supported in part by the US-Israel Binational Science Foundation grant 2016732.

Cite AsGet BibTex

Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.22

Abstract

This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(log² n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the Ω(n log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(log² n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing Θ̃(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that Θ̃(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster. Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(log n) time and O(n log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(log n) time (with failure probability O(1 / log^{Ω(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm’s time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c. Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Discrete mathematics
Keywords
  • Leader election
  • Asynchronous systems
  • Randomized algorithms
  • Singularly optimal
  • Complete networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Yehuda Afek and Eli Gafni. Time and message bounds for election in synchronous and asynchronous complete networks. SICOMP, 20(2):376-394, 1991. Google Scholar
  2. Yehuda Afek and Yossi Matias. Elections in anonymous networks. Information and Computation, 113(2):312-330, 1994. Google Scholar
  3. Dana Angluin. Local and global properties in networks of processors (extended abstract). In STOC, pages 82-93, 1980. URL: https://doi.org/10.1145/800141.804655.
  4. John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Upfal. Towards robust and efficient distributed computation in dynamic peer-to-peer networks. In SODA, pages 551-569, 2012. Google Scholar
  5. Baruch Awerbuch, Israel Cidon, and Shay Kutten. Communication-optimal maintenance of replicated information. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 492-502. IEEE, 1990. Google Scholar
  6. Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. A trade-off between information and communication in broadcast protocols. J. ACM, 37:238-256, 1990. Google Scholar
  7. Mike Burrows. The chubby lock service for loosely-coupled distributed systems. In 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2006. Google Scholar
  8. Miguel Castro, Peter Druschel, A-M Kermarrec, and Antony IT Rowstron. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in communications, 20(8):1489-1499, 2002. Google Scholar
  9. Tushar D Chandra, Robert Griesemer, and Joshua Redstone. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 398-407, 2007. Google Scholar
  10. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), 26(2):1-26, 2008. Google Scholar
  11. Michael Elkin. A simple deterministic distributed mst algorithm, with near-optimal time and message complexities. In PODC, pages 157-163, 2017. Google Scholar
  12. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Programming Languages & systems (TOPLAS), 5(1):66-77, January 1983. URL: https://doi.org/10.1145/357195.357200.
  13. Saurabh Ganeriwal, Ram Kumar, and Mani B. Srivastava. Timing-sync protocol for sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, SenSys 2003, Los Angeles, California, USA, November 5-7, 2003, pages 138-149, 2003. Google Scholar
  14. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The google file system. In Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29-43, 2003. Google Scholar
  15. Robert Gmyr and Gopal Pandurangan. Time-message trade-offs in distributed algorithms. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 32:1-32:18, 2018. Google Scholar
  16. Indranil Gupta, Robbert van Renesse, and Kenneth P. Birman. A probabilistically correct leader election protocol for large groups. In Proceedings of the 14th International Conference on Distributed Computing, DISC '00, pages 89-103, 2000. URL: http://dl.acm.org/citation.cfm?id=645957.675964.
  17. Bernhard Haeupler, D Ellis Hershkowitz, and David Wajc. Round-and message-optimal distributed graph algorithms. In PODC, pages 119-128, 2018. Google Scholar
  18. Pierre A. Humblet. Selecting a leader in a clique in O(n log n) messages. Memo, Lab. for Information & Decision Systems, MIT, 1984. Google Scholar
  19. Michael Isard. Autopilot: automatic data center management. ACM SIGOPS Operating Systems Review, 41(2):60-67, 2007. Google Scholar
  20. Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. In Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, PODC '08, pages 263-272, New York, NY, USA, 2008. ACM. URL: https://doi.org/10.1145/1400751.1400787.
  21. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. In SODA, pages 990-999, 2006. Google Scholar
  22. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. In FOCS, pages 87-98, 2006. URL: https://doi.org/10.1109/FOCS.2006.77.
  23. Ephraim Korach, Shay Kutten, and Shlomo Moran. A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans. Programming Languages & Systems (TOPLAS), 12(1):84-101, January 1990. URL: https://doi.org/10.1145/77606.77610.
  24. Ephraim Korach, Shlomo Moran, and Shmuel Zaks. Tight lower and upper bounds for some distributed algorithms for a complete network of processors. In Proceedings of the third annual ACM symposium on Principles of distributed computing, pages 199-207, New York, NY, USA, 1984. ACM. URL: https://doi.org/10.1145/800222.806747.
  25. Ephraim Korach, Shlomo Moran, and Shmuel Zaks. The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Computing, 16(2):231-236, 1987. URL: https://doi.org/10.1137/0216019.
  26. Ephraim Korach, Shlomo Moran, and Shmuel Zaks. Optimal lower bounds for some distributed algorithms for a complete network of processors. Theoretical Computer Science, 64(1):125-132, 1989. URL: https://doi.org/10.1016/0304-3975(89)90103-5.
  27. Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly optimal randomized leader election. CoRR, abs/2008.02782, 2020. URL: http://arxiv.org/abs/2008.02782.
  28. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On the complexity of universal leader election. J. ACM, 62:7, 2015. Google Scholar
  29. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. Sublinear bounds for randomized leader election. Theoretical Computer Science, 561:134-143, 2015. Google Scholar
  30. Shay Kutten and Dmitry Zinenko. Low communication self-stabilization through randomization. In DISC, pages 465-479. Springer, 2010. Google Scholar
  31. Gérard Le Lann. Distributed systems - towards a formal approach. In IFIP Congress, pages 155-160, 1977. Google Scholar
  32. Michael C. Loui, Teresa A. Matsushita, and Douglas B. West. Election in a complete network with a sense of direction. IPL, 22(4):185-187, 1986. Google Scholar
  33. Michael C. Loui, Teresa A. Matsushita, and Douglas B. West. Election in a complete network with a sense of direction. IPL, 28(6):327, 1988. URL: https://doi.org/10.1016/0020-0190(88)90181-0.
  34. Nancy Lynch. Distributed Algorithms. Morgan Kaufman Publishers, Inc., San Francisco, USA, 1996. Google Scholar
  35. Dahlia Malkhi, Michael Reiter, and Rebecca Wright. Probabilistic quorum systems. In PODC 1997, pages 267-273, New York, NY, USA, 1997. ACM. URL: https://doi.org/10.1145/259380.259458.
  36. Michael Mitzenmacher and Eli Upfal. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. Google Scholar
  37. Gopal Pandurangan. Distributed network algorithms. https://sites.google.com/site/gopalpandurangan/dna. Accessed: 2020-02-14.
  38. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. A time-and message-optimal distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 743-756. ACM, 2017. Google Scholar
  39. David Peleg. Time-optimal leader election in general networks. J. Parallel & Distributed Computing, 8(1):96-99, 1990. URL: https://doi.org/10.1016/0743-7315(90)90074-Y.
  40. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  41. Radia Perlman. Interconnections: bridges, routers, switches, and internetworking protocols. Addison-Wesley Professional, 2000. Google Scholar
  42. Gary Peterson. Efficient algorithms for elections in meshes and complete graphs. Technical report, TR 140, Dept. of CS, Univ. Rochester, 1985. Google Scholar
  43. Murali Krishna Ramanathan, Ronaldo A. Ferreira, Suresh Jagannathan, Ananth Grama, and Wojciech Szpankowski. Randomized leader election. Distributed Computing, pages 403-418, 2007. Google Scholar
  44. Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable content-addressable network. In SIGCOMM 2001, pages 161-172, New York, NY, USA, 2001. ACM. URL: https://doi.org/10.1145/383059.383072.
  45. Antony I. T. Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Middleware '01, pages 329-350. Springer-Verlag, 2001. URL: http://dl.acm.org/citation.cfm?id=646591.697650.
  46. Nicola Santoro. Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and Distributed Computing). Wiley-Interscience, 2006. Google Scholar
  47. Gurdip Singh. Efficient leader election using sense of direction. Distributed Computing, 10(3):159-165, 1997. URL: https://doi.org/10.1007/s004460050033.
  48. Gurdip Singh. Leader election in complete networks. SIAM J. Comput., 26(3):772-785, 1997. Google Scholar
  49. Andrew S. Tanenbaum and Maarten Van Steen. Distributed systems: principles and paradigms. Prentice-Hall, 2007. Google Scholar
  50. Gerard Tel. Introduction to distributed algorithms. Cambridge University Press, New York, NY, USA, 1994. Google Scholar
  51. Yong Yao and Johannes Gehrke. The cougar approach to in-network query processing in sensor networks. SIGMOD Record, 31(3):9-18, 2002. Google Scholar
  52. Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, and John D. Kubiatowicz. Tapestry: a resilient global-scale overlay for service deployment. IEEE J. Selected Areas in Communications, 22(1):41-53, January 2004. URL: https://doi.org/10.1109/JSAC.2003.818784.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact