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.OPODIS.2018.30
URN: urn:nbn:de:0030-drops-100901
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10090/
Sudo, Yuichi ;
Ooshita, Fukuhito ;
Kakugawa, Hirotsugu ;
Masuzawa, Toshimitsu ;
Datta, Ajoy K. ;
Larmore, Lawrence L.
Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time
Abstract
A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.
BibTeX - Entry
@InProceedings{sudo_et_al:LIPIcs:2018:10090,
author = {Yuichi Sudo and Fukuhito Ooshita and Hirotsugu Kakugawa and Toshimitsu Masuzawa and Ajoy K. Datta and Lawrence L. Larmore},
title = {{Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time}},
booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
pages = {30:1--30:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-098-9},
ISSN = {1868-8969},
year = {2018},
volume = {125},
editor = {Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10090},
URN = {urn:nbn:de:0030-drops-100901},
doi = {10.4230/LIPIcs.OPODIS.2018.30},
annote = {Keywords: Loose-stabilization, Population protocols, and Leader election}
}
|
Keywords: |
|
Loose-stabilization, Population protocols, and Leader election |
|
Collection: |
|
22nd International Conference on Principles of Distributed Systems (OPODIS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
15.01.2019 |
