Self-stabilization: randomness to reduce space.
T Herman:
Postscript Document and
DVI file.
Abstract
It is shown that Dijkstra's k-state self-stabilizing
protocol for mutual exclusion in a unidirectional ring can be
converted to a 3-state protocol by replacing a counter with
a random number generator.