### On the Complexity of Universal Leader ElectionOn the Complexity of Universal Leader Election

Access Restriction
Subscribed

 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

Source: ACM Digital Library