Probabilistic self-stabilization.
T Herman:
Postscript Document and
DVI file.
Abstract
A probabilistic self-stabilizing algorithm for a
ring of identical processes is presented;
the number of processes in the ring is odd,
the processes operate synchronously,
and communication is unidirectional in the ring.
The normal function of the algorithm is to circulate a
single token in the ring. If the initial state
of the ring is abnormal, i.e. the
number of tokens differs from one,
then execution of the algorithm results
probabilistically in
convergence to a normal state with one token.