main-content

Published in:

21-05-2019

# The complexity of leader election in diameter-two networks

Authors: Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson

Published in: Distributed Computing | Issue 2/2020

## Abstract

This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1–7:27, 2015) showed a fundamental lower bound of $$\varOmega (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., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134–143, 2015) established a tight bound of $$\tilde{\varTheta }(\sqrt{n})$$ 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 $$\tilde{\varTheta }(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 fixed positive constant c) succeeds and uses $$O(n\log ^3{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 $$\varOmega (n)$$ messages (even when n is known), regardless of the number of rounds. We also present an $$O(n\log {n})$$ message deterministic algorithm that takes $$O(\log {n})$$ rounds (but needs knowledge of n); we show that this message complexity is tight for deterministic algorithms. 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.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Maschinenbau + Werkstoffe

Testen Sie jetzt 15 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Appendix
Available only for authorised users
Footnotes
1
Throughout, “with high probability” means with probability at least $$1 - n^{-c}$$, for some fixed positive constant c.

2
Afek and Gafni [1] show the $$\varOmega (n\log {n})$$ message lower bound for complete networks under the non-simultaneous wakeup model in synchronous networks. As we have verified in our private communications with Shay Kutten (Professor, Technion), the same message bound can be shown to hold in the simultaneous wake-up model as well under the restriction that the number of rounds is bounded by a function of n.

3
We point out that lower bounds for complete networks do not directly translate to diameter-two networks.

4
If one assumes the KT1 model, where nodes have an initial knowledge of the IDs of their neighbors, there exists a trivial algorithm for leader election in a diameter-two graph that uses only O(n) messages.

5
This lower bound assumes non-simultaneous wakeup though. If nodes are assured to wake up at the same time in synchronous complete networks, there exists a trivial algorithm: if a node’s identity is some i, it waits i time before it sends any message then leader election could be solved (deterministically) in O(n) messages on complete graphs in synchronous networks. As we have verified in our private communications with Shay Kutten (Professor, Technion), the same message bound can be shown to hold in the simultaneous wake-up model as well under the restriction that the number of rounds is bounded by a function of n.

6
This enumeration is used only for the description of the lower bound construction and is unbeknownst to the nodes.

7
We note that this is the main idea borrowed from the Afek–Gafni algorithm [1]—the number of messages sent by each “active” node increases exponentially in every phase. That effect is, however, counterbalanced by the exponentially decreasing number of “active” nodes.

8
In contrast, we note that $$\varOmega (m)$$ is a lower bound for deterministic on graphs of diameter at least three, even if n is known [10].

Literature
1.
Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. Comput. 20(2), 376–394 (1991). https://​doi.​org/​10.​1137/​0220023
2.
Gilbert, S., Robinson, P., Sourav, S.: Leader election in well-connected graphs. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pp. 227–236. ACM, New York, NY, USA (2018). https://​doi.​org/​10.​1145/​3212734.​3212754
3.
Gilbert, S., Robinson, P., Sourav, S.: Slow links, fast links, and the cost of gossip. In: 2018 IEEE 38th International Conference on Distributed Computing Systems, ICDCS ’18, pp. 786–796 (2018). https://​doi.​org/​10.​1109/​ICDCS.​2018.​00081
4.
Humblet, P.A.: Electing a Leader in a Clique in $$O(n\log {n})$$ Messages. Intern. Memo., Laboratory for Information and Decision Systems, MIT, Cambridge (1984)
5.
Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. Distrib. Comput. 25(3), 189–205 (2012). https://​doi.​org/​10.​1007/​s00446-012-0157-9
6.
Korach, E., Kutten, S., Moran, S.: A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans. Program. Lang. Syst. (TOPLAS) 12(1), 84–101 (1990). https://​doi.​org/​10.​1145/​77606.​77610 CrossRef
7.
Korach, E., Moran, S., Zaks, S.: 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, pp. 199–207. ACM, New York, NY, USA (1984). https://​doi.​org/​10.​1145/​800222.​806747
8.
Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Comput. 16(2), 231–236 (1987). https://​doi.​org/​10.​1137/​0216019
9.
Korach, E., Moran, S., Zaks, S.: Optimal lower bounds for some distributed algorithms for a complete network of processors. Theor. Comput. Sci. 64(1), 125–132 (1989). https://​doi.​org/​10.​1016/​0304-3975(89)90103-5
10.
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7:1–7:27 (2015). https://​doi.​org/​10.​1145/​2699440. Invited paper from ACM PODC 2013
11.
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci. 561(Part B), 134–143 (2015). https://​doi.​org/​10.​1016/​j.​tcs.​2014.​02.​009. Special Issue on Distributed Computing and Networking
12.
Le Lann, G.: Distributed systems—towards a formal approach. In: IFIP Congress, pp. 155–160 (1977)
13.
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996) MATH
14.
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edn. Cambridge University Press, Cambridge (2017) MATH
15.
Pai, S., Pandurangan, G. V., Pemmaraju, S., Riaz, T., Robinson, P.: Symmetry breaking in the congest model: Time- and message-efficient algorithms for ruling sets. In: 31st International Symposium on Distributed Computing, DISC 2017, October 16–20, 2017, pp. 38:1–38:16. Vienna, Austria (2017). https://​doi.​org/​10.​4230/​LIPIcs.​DISC.​2017.​38
16.
Peleg, D.: Time-optimal leader election in general networks. J. Parallel Distrib. Comput. 8(1), 96–99 (1990). https://​doi.​org/​10.​1016/​0743-7315(90)90074-Y CrossRef
17.
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000). https://​doi.​org/​10.​1137/​1.​9780898719772
18.
Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley Series on Parallel and Distributed Computing. Wiley, New York (2006) CrossRef
19.
Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, New York (2001) MATH
Title
The complexity of leader election in diameter-two networks
Authors
Soumyottam Chatterjee
Gopal Pandurangan
Peter Robinson
Publication date
21-05-2019
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing / Issue 2/2020
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-019-00354-2

Go to the issue