Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time

We study the self-stabilizing leader election (SS-LE) problem in the population protocol model, assuming exact knowledge of the population size n. Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [BCC+21] (PODC) showed that this problem can be solved in O(n) expected time with O(n) states. Recently, Gąsieniec, Grodzicki, and Stachowiak [GGS25] (PODC) proved that n + O (log n) states suffice to achieve O(n log n) time both in expectation and with high probability (w.h.p.). If substantially more states are available, sublinear time can be achieved. The authors of [BCC+21] presented a 2O(nρ)-state SS-LE protocol with a parameter ρ: setting ρ = Θ(log n) yields an optimal O(log n) time both in expectation and w.h.p., while ρ = Θ(1) results in O(ρn1/(ρ+1)) expected time. Recently, Austin, Berenbrink, Friedetzky, Götte, and Hintze [ABF+25] (PODC) presented a novel SS-LE protocol parameterized by a positive integer ρ with 1 ≤ ρ < n/2 that solves SS-LE in O(n/ρ · log n) time w.h.p. using 2O(ρ2 log n) states. This paper independently presents yet another time-space tradeoff of SS-LE: for any positive integer ρ with 2≤ρ≤n, SS-LE can be achieved within O(n/ρ · log ρ) expected time using 22ρlg2 ρ + O(log n) states. The proposed protocol uses significantly fewer states than [ABF+25] for any expected stabilization time above Θ(nlog⁡n). When ρ = Θ(log n/log2 log n), the proposed protocol is the first to achieve sublinear time while using only polynomially many states. A limitation of our protocol is that the constraint ρ≤n prevents achieving o(nlog⁡n) time, whereas the protocol of [ABF+25] can surpass this bound.