Self-Stabilizing token circulation on an asynchronous ring

Laurent Rosaz

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


In [], J. Beauquier, M. Gradinariu and C.Johnen provide a probabilistic algorithm which self-stabilizes from a configuration containing at least one token to the circulation of a single token on an asynchronous anonymous unidirectional ring. In this paper, we compute the message complexity of the stabilization period of the [] algorithm (which is theta(N^3)), we provide a better algorithm and compute the message complexity of that better algorithm (which is theta(N^2 ln N)). Such algorithms can be useful in particular for mutual exclusion.