ABSTRACT
Leader election is one of the fundamental problems in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message complexity of leader election in synchronous distributed networks, in particular, in networks of diameter two. Kutten et al. [JACM 2015] showed a fundamental lower bound of Ω(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability; this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., diameter 1), Kutten et al. [TCS 2015] established a tight bound of Θ(√n)1 on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known.
In this paper, we settle this complexity by showing a tight bound of Θ(n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 -- n-c, for some positive constant c) succeeds and uses O (n log3 n) messages and runs in O (1) rounds; this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs Ω(n) messages (even when n is known), regardless of the number of rounds. We also present an O (n log n) messages deterministic algorithm that takes O (log n) rounds (but needs knowledge of n); we show that this message complexity is tight for deterministic algorithms.
Our results show that leader election can be solved in diameter-two graphs in (essentially) linear (in n) message complexity and thus the Ω(m) lower bound does not apply to diameter-two graphs. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-à-vis the graph diameter.
- Yehuda Afek and Eli Gafni. Time and message bounds for election in synchronous and asynchronous complete networks. SIAM Journal of Computing, 20(2):376--394, 1991. Google ScholarDigital Library
- Seth Gilbert, Peter Robinson, and Suman Sourav. Brief announcement: Gossiping with latencies. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 255--257, 2017. Google ScholarDigital Library
- P Humblet. Electing a leader in a clique in O (n log n) messages. Intern. Memo., Laboratory for Information and Decision Systems, M.I.T., Cambridge, Mass, 1984.Google Scholar
- 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. Google ScholarDigital Library
- E. Korach, S. Kutten, and S. Moran. A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans. Program. Lang. Syst., 12(1):84--101, January 1990. Google ScholarDigital Library
- E. Korach, S. Moran, and S. 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, PODC '84, pages 199--207, New York, NY, USA, 1984. ACM. Google ScholarDigital Library
- E. Korach, S. Moran, and S. Zaks. The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM Journal on Computing, 16(2):231--236, 1987. Google ScholarDigital Library
- E. Korach, S. Moran, and S. Zaks. Optimal lower bounds for some distributed algorithms for a complete network of processors. Theoretical Computer Science, 64(1):125--132, 1989. Google ScholarDigital Library
- Shay Kutten. Private communication. 2017.Google Scholar
- Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On the complexity of universal leader election. Journal of the ACM, 62(1):7:1--7:27, March 2015. Invited paper from ACM PODC 2013. Google ScholarDigital Library
- Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. Sublinear bounds for randomized leader election. Theoretical Computer Science, 561, Part B:134--143, 2015. Special Issue on Distributed Computing and Networking. Google ScholarDigital Library
- Gérard Le Lann. Distributed systems - towards a formal approach. In IFIP Congress, pages 155--160, 1977.Google Scholar
- Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996. Google ScholarDigital Library
- Michael Mitzenmacher and Eli Upfal. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Google ScholarDigital Library
- Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry breaking in the CONGEST model: Time- and message-efficient algorithms for ruling sets. In DISC 2017, Vienna, to appear.Google ScholarDigital Library
- David Peleg. Time-optimal leader election in general networks. Journal of Parallel and Distributed Computing, 8(1):96--99, 1990. Google ScholarDigital Library
- David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google ScholarDigital Library
- Nicola Santoro. Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and Distributed Computing). Wiley-Interscience, 2006. Google ScholarDigital Library
- Gerard Tel. Introduction to distributed algorithms. Cambridge University Press, New York, NY, USA, 1994. Google ScholarDigital Library
- The Complexity of Leader Election: A Chasm at Diameter Two
Recommendations
On the Complexity of Universal Leader Election
Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in ...
Sublinear bounds for randomized leader election
This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O ( 1 ) rounds and (with high probability) uses only O ( n log 3 / 2 n ) ...
Brief Announcement: On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed ComputingThis paper investigates on the message complexity of the two fundamental problems, namely, leader election and agreement in the crash-fault synchronous and fully-connected distributed network. We present randomized algorithms for both the problems and ...
Comments