The Complexity of Leader Election: A Chasm at Diameter Two

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.

References

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. Shay Kutten. Private communication. 2017.
10. 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.
11. 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.
12. Gérard Le Lann. Distributed systems - towards a formal approach. In IFIP Congress, pages 155--160, 1977.
13. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
14. Michael Mitzenmacher and Eli Upfal. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
15. 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.
16. David Peleg. Time-optimal leader election in general networks. Journal of Parallel and Distributed Computing, 8(1):96--99, 1990.
17. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
18. Nicola Santoro. Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and Distributed Computing). Wiley-Interscience, 2006.
19. Gerard Tel. Introduction to distributed algorithms. Cambridge University Press, New York, NY, USA, 1994.

• Computer systems organization

  • Architectures

• Theory of computation

  • Design and analysis of algorithms