Selected Problems in Self‑Stabilising Population Protocols

18^th February 2026, 13:00 GH223
Leszek Gasieniec
University of Liverpool

Abstract

Population protocols offer a foundational framework for studying the computational potential of systems composed of simple, indistinguishable agents that interact in pairs. Each agent operates with limited memory, represented solely by its current state drawn from a fixed state space. In the classical formulation, a protocol begins from a well‑defined initial configuration encoding the input and is required to stabilise to a correct final configuration that represents the solution to the problem at hand. In contrast, self‑stabilising population protocols relax this assumption and allow the system to start from any arbitrary configuration of states. A self‑stabilising protocol must guarantee that, irrespective of the initial configuration, the system eventually converges to a correct and stable configuration.

This presentation will focus on several key tasks within this setting, including ranking, leader election, and distributed positioning (in model augmented with geometric or spatial queries). The discussion will draw on recent advances in the area, such as improved efficiency results for near‑state and state‑optimal self‑stabilising leader election protocols [1], as well as new techniques for anonymous self‑stabilising localisation using spatial population protocols [2].

References
[1] Leszek Gasieniec, Tytus Grodzicki, Grzegorz Stachowiak: Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols. PODC 2025: 510–520.
[2] Leszek Gasieniec, Lukasz Kuszner, Ehsan Latif, Ramviyas Parasuraman, Paul G. Spirakis, Grzegorz Stachowiak: Anonymous Self-Stabilising Localisation via Spatial Population Protocols. ISAAC 2025: 35:1–35:17.

Additional Materials

• https://dl.acm.org/doi/10.1145/3732772.3733528