2026-08-16T16:54:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10090 2024-03-06T10:45:35Z ddc:004 open_access

Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time Sudo, Yuichi Ooshita, Fukuhito Kakugawa, Hirotsugu Masuzawa, Toshimitsu Datta, Ajoy K. Larmore, Lawrence L. Loose-stabilization Population protocols and Leader election 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuichi Sudo and Fukuhito Ooshita and Hirotsugu Kakugawa and Toshimitsu Masuzawa and Ajoy K. Datta and Lawrence L. Larmore 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.30 urn:nbn:de:0030-drops-100901 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.30 eng https://creativecommons.org/licenses/by/3.0/legalcode