Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Distributed Computing 2/2020

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

Login to get access
share
SHARE

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.

To get access to this content you need the following product:

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
  • Business IT + Informatik
  • 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
  • Business IT + Informatik
  • 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
  • Business IT + Informatik
  • 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
4.
go back to reference 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) 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)
7.
go back to reference 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 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
12.
go back to reference Le Lann, G.: Distributed systems—towards a formal approach. In: IFIP Congress, pp. 155–160 (1977) Le Lann, G.: Distributed systems—towards a formal approach. In: IFIP Congress, pp. 155–160 (1977)
13.
go back to reference Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996) MATH Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996) MATH
14.
go back to reference Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edn. Cambridge University Press, Cambridge (2017) MATH Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edn. Cambridge University Press, Cambridge (2017) MATH
15.
18.
go back to reference Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley Series on Parallel and Distributed Computing. Wiley, New York (2006) CrossRef Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley Series on Parallel and Distributed Computing. Wiley, New York (2006) CrossRef
19.
go back to reference Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, New York (2001) MATH Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, New York (2001) MATH
Metadata
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

Other articles of this Issue 2/2020

Distributed Computing 2/2020 Go to the issue

Premium Partner