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 (n) using 2^O (n² 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 (n^{ n n) } states for the same time bound. In general, for 1 r n/2, our protocol requires 2^O (r²n) states and stabilizes in time O ( (nn) /r), w. h. p. ; the above result is achieved for r= (n). For r=²n our protocol requires only sub-linear time using only 2^O (³ n) states, resolving an open problem stated in that paper. Sublinear-Time-SSR requires O (n n^1/ (H+1) ) time using 2^ (nH) n states for all 1 H (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.