A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States

DOI10.1145/3583668.3594586arXiv2305.08375OpenAlexW4380881564WikidataQ130964658 ScholiaQ130964658MaRDI QIDQ6202212FDOQ6202212

Authors: Yuichi Sudo, Fukuhito Ooshita, Toshimitsu Masuzawa 

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We propose a self-stabilizing leader election (SS-LE) protocol on ring networks in the population protocol model. Given a rough knowledge $psi=lceillognceil+O(1)$ on the population size $n$, the proposed protocol lets the population reach a safe configuration within $O(n^{2}logn)$ steps with high probability starting from any configuration. Thereafter, the population keeps the unique leader forever. Since no protocol solves SS-LE in $o(n^2)$ steps with high probability, the convergence time is near-optimal: the gap is only an $O(logn)$ multiplicative factor. This protocol uses only $polylog(n)$ states. There exist two state-of-the-art algorithms in current literature that solve SS-LE on ring networks. The first algorithm uses a polynomial number of states and solves SS-LE in $O(n^2)$ steps, whereas the second algorithm requires exponential time but it uses only a constant number of states. Our proposed algorithm provides an excellent middle ground between these two.

Full work available at URL: https://arxiv.org/abs/2305.08375

zbMATH Keywords

leader electionself-stabilizationpopulation protocols

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Computation in networks of passively mobile finite-state sensors
• Self-stabilizing systems in spite of distributed control
• Memory-efficient and self-stabilizing network RESET (extended abstract)
• Fast computation by population protocols with a leader
• Loosely-stabilizing leader election in a population protocol model
• Determining majority in networks with local interactions and very small local memory
• Loosely-stabilizing leader election with polylogarithmic convergence time
• How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
• On space and time complexity of loosely-stabilizing leader election
• Time-space trade-offs in population protocols
• Space-optimal proportion consensus with population protocols
• Self-Stabilizing Leader Election
• Self-Stabilizing Leader Election in Regular Graphs

This page was built for publication: A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202212)