NDLI: On the Complexity of Universal Leader Election

Content Provider	ACM Digital Library
Author	Kutten, Shay Pandurangan, Gopal Peleg, David Robinson, Peter Trehan, Amitabh
Copyright Year	2015
Abstract	Electing a leader is a fundamental task in distributed computing. In its $\textit{implicit}$ version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of $\textit{randomized}$ implicit leader election in synchronous distributed networks. Surprisingly, the most “obvious” complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of $Ω(\textit{m})$ messages, where $\textit{m}$ is the number of edges in the network, and $Ω(\textit{D})$ time, where $\textit{D}$ is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even $Ω(\textit{n}),$ where $\textit{n}$ is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that $\textit{D}$ and $\textit{n}$ were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every $\textit{D},$ $\textit{m},$ and $\textit{n},$ and hold even if $\textit{D},$ $\textit{m},$ and $\textit{n}$ are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an $\textit{O}(\textit{m})$ messages algorithm. An $\textit{O}(\textit{D})$ time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an $Ω(\textit{m})$ message lower bound for randomized broadcast algorithms. An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.
Starting Page	1
Ending Page	27
Page Count	27
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2699440
Journal	Journal of the ACM (JACM)
Volume Number	62
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-03-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Leader election Distributed algorithm Lower bound
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the communication complexity of distributed algebraic computation

Bit complexity of breaking and achieving symmetry in chains and rings

A Lower Bound on the Complexity of Orthogonal Range Queries

On the complexity of universal leader election

Optimal maintenance of a spanning tree

Lower bounds on communication complexity in distributed computer networks

Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

Tight lower bounds for probabilistic solitude verification on anonymous rings

Cosmological lower bound on the circuit complexity of a small problem in logic

On the Complexity of Universal Leader Election

Similar Documents

On the communication complexity of distributed algebraic computation

Bit complexity of breaking and achieving symmetry in chains and rings

A Lower Bound on the Complexity of Orthogonal Range Queries

On the complexity of universal leader election

Optimal maintenance of a spanning tree

Lower bounds on communication complexity in distributed computer networks

Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

Tight lower bounds for probabilistic solitude verification on anonymous rings

Cosmological lower bound on the circuit complexity of a small problem in logic

On the Complexity of Universal Leader Election