Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient

Abstract

We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1,\dots ,n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n+O(\log n)$ states. Our protocol stabilizes in $O(n^2\log n)$ interactions w.h.p.\ and in expectation, using $n+O({\log }^{2}n)$ states in total. Our stabilization time is asymptotically optimal (see Burman et al., PODC'21). In comparison to the currently best known ranking protocol by Burman et al., which requires $n+\hat{I}\text{c◯}(n)$ states, our result exponentially improves the number of overhead states.

Accepted to ICDCS 2025