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.40
URN: urn:nbn:de:0030-drops-148427
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14842/
Sudo, Yuichi ;
Eguchi, Ryota ;
Izumi, Taisuke ;
Masuzawa, Toshimitsu
Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols
Abstract
We consider the leader election problem in the population protocol model. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e., the knowledge of the exact size of a network) and rich computational resource (i.e., the number of states). Loose-stabilization is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not necessarily forever. The main contribution of this paper is giving a time-optimal loosely-stabilizing leader election protocol. The proposed protocol with design parameter τ ≥ 1 attains O(τ log n) parallel convergence time and Ω(n^τ) parallel holding time (i.e., the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require Ω(τ log n) parallel time.
BibTeX - Entry
@InProceedings{sudo_et_al:LIPIcs.DISC.2021.40,
author = {Sudo, Yuichi and Eguchi, Ryota and Izumi, Taisuke and Masuzawa, Toshimitsu},
title = {{Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {40:1--40:17},
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/14842},
URN = {urn:nbn:de:0030-drops-148427},
doi = {10.4230/LIPIcs.DISC.2021.40},
annote = {Keywords: population protocols, leader election, loose-stabilization, self-stabilization}
}
Keywords: |
|
population protocols, leader election, loose-stabilization, self-stabilization |
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
04.10.2021 |