Time- and Space-Optimal Silent Self-Stabilizing Exact Majority in Population Protocols

Abstract

We address the self-stabilizing exact majority problem in the population protocol model, introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta (2004). In this model, there are $n$ state machines, called agents, which form a network. At each time step, only two agents interact with each other, and update their states. In the self-stabilizing exact majority problem, each agent has a fixed opinion, $\mathtt{A}$ or $\mathtt{B}$, and stabilizes to a safe configuration in which all agents output the majority opinion from any initial configuration. In this paper, we show the impossibility of solving the self-stabilizing exact majority problem without knowledge of $n$ in any protocol. We propose a silent self-stabilizing exact majority protocol, which stabilizes within $O(n)$ parallel time in expectation and within $O(n\log n)$ parallel time with high probability, using $O(n)$ states, with knowledge of $n$. Here, a silent protocol means that, after stabilization, the state of each agent does not change. We establish lower bounds, proving that any silent protocol requires $\hat{I}\text{c◯}(n)$ states, $\hat{I}\text{c◯}(n)$ parallel time in expectation, and $\hat{I}\text{c◯}(n\log n)$ parallel time with high probability to reach a safe configuration. Thus, the proposed protocol is time- and space-optimal.

Accepted to SSS 2025