License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.22
URN: urn:nbn:de:0030-drops-131002
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13100/
Kutten, Shay ;
Moses Jr., William K. ;
Pandurangan, Gopal ;
Peleg, David
Singularly Optimal Randomized Leader Election
Abstract
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(log² n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the Ω(n log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(log² n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing Θ̃(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that Θ̃(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster.
Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(log n) time and O(n log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(log n) time (with failure probability O(1 / log^{Ω(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm’s time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c.
Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks.
BibTeX - Entry
@InProceedings{kutten_et_al:LIPIcs:2020:13100,
author = {Shay Kutten and William K. Moses Jr. and Gopal Pandurangan and David Peleg},
title = {{Singularly Optimal Randomized Leader Election}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {22:1--22:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13100},
URN = {urn:nbn:de:0030-drops-131002},
doi = {10.4230/LIPIcs.DISC.2020.22},
annote = {Keywords: Leader election, Asynchronous systems, Randomized algorithms, Singularly optimal, Complete networks}
}
|
Keywords: |
|
Leader election, Asynchronous systems, Randomized algorithms, Singularly optimal, Complete networks |
|
Collection: |
|
34th International Symposium on Distributed Computing (DISC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
07.10.2020 |
