Service Time Optimal Self-Stabilizing Token Circulation Protocol on Anonymous Unidrectional Rings

We present a self-stabilizing token circulation protocol on unidirectional anonymous rings. This protocol does not required processor identifiers, no distinguished processor (i.e. all processors perform the same algorithm). The protocol is a randomized self-stabilizing, meaning that starting from an arbitrary configuration (in response to an arbitrary perturbation modifying the memory state), it reaches (with probability 1) a legitimate configuration (i.e. a configuration with only one token in the network). All previous randomized self-stabilizing token circulation protocols design to work under unfair distributed schedulers have the same drawback: once stabilized, the service time is slow (in the best case, it is bounded by ¡¢ where ¢ is the ring size). Once stabilized, our protocol provides an optimal service: after ¢ computation steps, each processor has obtained one time the token. The protocol can be used to implement a fair distributed mutual exclusion in any ring topology network