A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States

05/15/2023
by   Daisuke Yokota, et al.
0

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(n^2 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(n^2) 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(n^2) 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset