Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols

09/23/2020
by   Daisuke Yokota, et al.
0

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).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset