We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Theta (n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents’ states eventually stop changing. Observing that any silent protocol solving self-stabilizing leader election requires <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Omega (n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> expected parallel time, we introduce a silent protocol that uses optimal O(n) parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, but using at least exponential states (a quasipolynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$1,\ldots ,n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>.

Time-optimal self-stabilizing leader election in population protocols

期刊论文
出版模式：

开放获取
发表日期：

2026年8月3日

查看全文

Janna Burman,
Ho-Lin Chen,
Hsueh-Ping Chen,
David Doty,
Thomas Nowak,
Eric Severson,
Chuan Xu

摘要

We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time $\Theta (n^2)$ $Θ (n^{2})$ and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents’ states eventually stop changing. Observing that any silent protocol solving self-stabilizing leader election requires $\Omega (n)$ $Ω (n)$ expected parallel time, we introduce a silent protocol that uses optimal O(n) parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of $O(\log n)$ $O (log n)$ , but using at least exponential states (a quasipolynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks $1,\ldots ,n$ $1, \dots, n$ .