License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.27
URN: urn:nbn:de:0030-drops-148294
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14829/
Kutten, Shay ;
Moses Jr., William K. ;
Pandurangan, Gopal ;
Peleg, David
Singularly Near Optimal Leader Election in Asynchronous Networks
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 asynchronous networks.
Kutten et al. (JACM 2015) presented a singularly near optimal randomized leader election algorithm for general synchronous networks that ran in O(D) time and used O(m log n) messages (where D, m, and n are the network’s diameter, number of edges and number of nodes, respectively) with high probability. Both bounds are near optimal (up to a logarithmic factor), since Ω(D) and Ω(m) are the respective lower bounds for time and messages for leader election even for synchronous networks and even for (Monte-Carlo) randomized algorithms. On the other hand, for general asynchronous networks, leader election algorithms are only known that are either time or message optimal, but not both. Kutten et al. (DISC 2020) presented a randomized asynchronous leader election algorithm that is singularly near optimal for complete networks, but left open the problem for general networks.
This paper shows that singularly near optimal (up to polylogarithmic factors) bounds can be achieved for general asynchronous networks. We present a randomized singularly near optimal leader election algorithm that runs in O(D + log² n) time and O(m log² n) messages with high probability. Our result is the first known distributed leader election algorithm for asynchronous networks that is near optimal with respect to both time and message complexity and improves over a long line of results including the classical results of Gallager et al. (ACM TOPLAS, 1983), Peleg (JPDC, 1989), and Awerbuch (STOC, 89).
BibTeX - Entry
@InProceedings{kutten_et_al:LIPIcs.DISC.2021.27,
author = {Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
title = {{Singularly Near Optimal Leader Election in Asynchronous Networks}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {27:1--27:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14829},
URN = {urn:nbn:de:0030-drops-148294},
doi = {10.4230/LIPIcs.DISC.2021.27},
annote = {Keywords: Leader election, Singular optimality, Randomized algorithms, Asynchronous networks, Arbitrary graphs}
}
|
Keywords: |
|
Leader election, Singular optimality, Randomized algorithms, Asynchronous networks, Arbitrary graphs |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
