**
Self-Stabilizing Symmetry Breaking in Constant-Space.
**

*
Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung.
*

**
Abstract:
**
We investigate the problem of self-stabilizing round-robin token
management scheme on an anonymous bidirectional ring of identical
processors, where each processor is an asynchronous probabilistic
(coin-flipping) finite state machine which sends and receives
messages. We show that the solution to this problem is equivalent to
symmetry breaking (i.e., leader election). Requiring only
constant-size messages and message-passing model has practical
implications: our solution can be implemented in high-speed networks
using a universal fast hardware switches (i.e., finite state machines)
of size * independent* of the size of the network.

Our automata-based message-passing model has inherent deadlock possibility (i.e., when all processors are waiting for a message) which we assume is detected by an external timeout mechanism. Provided that there is no deadlock to begin with, we show how starting from an arbitrary configuration, the system never enters a deadlock state and further stabilizes in polynomial time. We note that Dijkstra showed that the last problem does not have a deterministic solution (even when the identical processors possess an arbitrary power): starting from a ring with a multitude of tokens, any deterministic system will either not stabilize or will enter a deadlock state.

**comment:**
Appeared In Proceedings of 24th annual ACM Symposium on Theory of
Computing (STOC-92) May 4-6, 1992, Victoria, British Columbia, Canada

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |