A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols

We consider the problem of self-stabilizing leader election in the population model by Angluin, Aspnes, Diamadi, Fischer, and Peralta (JDistComp '06). The population model is a well-established and powerful model for asynchronous, distributed computation with a large number of applications. For self-stabilizing leader election, the population of n anonymous agents, interacting in uniformly random pairs, must stabilize with a single leader from any possible initial configuration. The focus of this paper is to develop time-efficient self-stabilizing protocols whilst minimizing the number of states. We present a parametrized protocol, which, for a suitable setting, achieves the asymptotically optimal time O(log n) using 2O(n²log n) states (throughout the paper, ``time'' refers to ``parallel time'', i.e., the number of pairwise interactions divided by n). This is a significant improvement over the previously best protocol Sublinear-Time-SSR due to Burman, Chen, Chen, Doty, Nowak, Severson, and Xu (PODC '21), which requires 2^O(nlog nlog n) states for the same time bound. In general, for 1≤ r≤ n/2, our protocol requires 2^O(r²logn) states and stabilizes in time O((nlogn)/r), w.h.p.; the above result is achieved for r=Θ(n). For r=log²n our protocol requires only sub-linear time using only 2O(log³ n) states, resolving an open problem stated in that paper. Sublinear-Time-SSR requires O(log n· n1/(H+1)) time using 2Θ(nH) · log n states for all 1≤ H≤Θ(log n). Similar to previous works, it solves leader election by assigning a unique rank from $1$ through n to each agent. The principal bottleneck for self-stabilizing ranking usually is to detect if there exist agents with the same rank. One of our main conceptual contributions is a novel technique for collision detection.