Access Restriction

Author Kutten, Shay ♦ Pandurangan, Gopal ♦ Peleg, David ♦ Robinson, Peter ♦ Trehan, Amitabh
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Leader election ♦ Distributed algorithm ♦ Lower bound
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-03-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 1
Page Count 27
Starting Page 1
Ending Page 27

Open content in new tab

   Open content in new tab
Source: ACM Digital Library