2025/05/29 by Sudo, Yuichi
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2505.23649
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 (PODC 2021) showed that this problem can be solved in O(n) expected time with O(n) states. Recently, Gąsieniec, Grodzicki, and Stachowiak (PODC 2025) 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. Burman~et~al.~(PODC 2021) presented a 2O(nρlog 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. Very recently, Austin, Berenbrink, Friedetzky, Götte, and Hintze (PODC 2025) presented a novel SS-LE protocol parameterized by a positive integer ρ with 1 ≤ ρ< n/2 that solves SS-LE in O(\fracnρ⋅log n) time w.h.p. using 2O(ρ2log n) states. This paper independently presents yet another time--space tradeoff of SS-LE: for any positive integer ρ with 1 ≤ ρ≤ √(n), SS-LE can be achieved within O(\fracnρ⋅ logρ) expected time using 22ρ\lgρ+ O(log n) states. The proposed protocol uses significantly fewer states than the protocol of Austin~et~al. requires to achieve any expected stabilization time above Θ(√(n)log n). When ρ= Θ((log n)/(log 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(√(n)log n) time, whereas the protocol of Austin et~al. can surpass this bound.