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