We propose a self-stabilizing leader election (SS-LE) protocol on ring networks in the population protocol model. Given a rough knowledge ψ = ⌈log n⌉ + O(1) on the population size n, the proposed protocol lets the population reach a safe configuration within O(n2 log n) steps with high probability starting from any configuration. Thereafter, the population keeps the unique leader forever. Since no protocol solves SS-LE in o(n2) steps with high probability, the convergence time is near-optimal: the gap is only an O(log n) multiplicative factor. This protocol uses only polylog(n) states. There exist two state-of-the-art algorithms in current literature that solve SS-LE on ring networks. The first algorithm uses a polynomial number of states and solves SS-LE in O(n2) steps, whereas the second algorithm requires exponential time but it uses only a constant number of states. Our proposed algorithm provides an excellent middle ground between these two.

We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound N on the population size n, the proposed protocol elects a unique leader within O(nN) expected steps starting from any configuration and uses O(N) states. This convergence time is optimal if a given upper bound N is asymptotically tight, i.e., N=O(n).