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

DOI10.1145/3583668.3594586MaRDI QIDQ6202212zbMATH OpenOpenAlexWikidataFDO

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)

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)

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.

Cites work

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

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)