Randomized three-state alternator for uniform rings

In this paper, we propose a three-state alternator algorithm for uniform ring with n processors, where n>1. The proposed algorithm is a randomized algorithm and operates correctly for synchronous mode. An alternator is a self-stabilization system that satisfies the following properties. (1) The safety property: if a processor executes the critical step, no neighbor executes the critical step at the same computing phase. (2) The liveness property: along any infinite computing phases, every processor executes the critical step infinitely often.An alternator is 1-fair if between any two consecutive critical steps of a processor, all other processors execute the critical step exactly once. The proposed alternator is 1-fair. It allows each processor to execute the critical step every three phases.The proposed algorithm has the snap property in the sense that the system satisfies the safety property of the alternator even if some transient fault occurs. The worst-case stabilization time of the algorithm is an expected number of two phases plus a deterministic number of at most 2(n-2) phases.