Search papers, labs, and topics across Lattice.
This paper presents a probabilistic self-stabilizing leader election algorithm for arbitrary anonymous networks that achieves $O(\log \log n)$ bits of memory per node, improving upon existing solutions that typically require $\Omega(\log n)$ bits for general graphs. The algorithm operates in the state model under a synchronous scheduler, assuming knowledge of a global parameter $N = \Theta(\log n)$, and achieves convergence to a stable configuration with a unique leader almost surely. The analysis demonstrates that the system stabilizes within $O(\mathrm{poly}(n))$ rounds with high probability, despite not verifying the silence property or providing explicit termination detection.
Electing a leader in a network can now be done with just $O(\log \log n)$ bits of memory per node, even in arbitrary anonymous networks.
We study the self-stabilizing leader election problem in anonymous $n$-nodes networks. Achieving self-stabilization with low space memory complexity is particularly challenging, and designing space-optimal leader election algorithms remains an open problem for general graphs. In deterministic settings, it is known that $\Omega(\log \log n)$ bits of memory per node are necessary [Blin et al., Disc. Math. \&Theor. Comput. Sci., 2023], while in probabilistic settings the same lower bound holds for some values of $n$, but only for an unfair scheduler [Beauquier et al., PODC 1999]. Several deterministic and probabilistic protocols have been proposed in models ranging from the state model to the population protocols. However, to the best of our knowledge, existing solutions either require $\Omega(\log n)$ bits of memory per node for general worst case graphs, or achieve low state complexity only under restricted network topologies such as rings, trees, or bounded-degree graphs. In this paper, we present a probabilistic self-stabilizing leader election algorithm for arbitrary anonymous networks that uses $O(\log \log n)$ bits of memory per node. Our algorithm operates in the state model under a synchronous scheduler and assumes knowledge of a global parameter $N = \Theta(\log n)$. We show that, under our protocol, the system converges almost surely to a stable configuration with a unique leader and stabilizes within $O(\mathrm{poly}(n))$ rounds with high probability. To achieve $O(\log \log n)$ bits of memory, our algorithm keeps transmitting information after convergence, i.e. it does not verify the silence property. Moreover, like most works in the field, our algorithm does not provide explicit termination detection (i.e., nodes do not detect when the algorithm has converged).
