Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

21-05-2019 | Issue 2/2020

Distributed Computing 2/2020

The complexity of leader election in diameter-two networks

Journal:
Distributed Computing > Issue 2/2020
Authors:
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
Important notes
A preliminary version of this work was nominated for the best paper award at the 19th International Conference on Distributed Computing and Networking (ICDCN 2018).
Gopal Pandurangan was supported, in part, by NSF Grants CCF-1527867, CCF-1540512, IIS-1633720, and CCF-1717075 and by US-Israel BSF Grant 2016419.
Peter Robinson was supported, in part, by the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2018-06322.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

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.

Please log in to get access to this content

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 + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 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 + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 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 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 2/2020

Distributed Computing 2/2020 Go to the issue

Premium Partner

    Image Credits