Self-Stabilizing Ring Orientation Using Constant Space

AbstractThe ring-orientation problem requires all processors on an anonymous ring to reach agreement on a direction along the ring. A self-stabilizing ring-orientation protocol eventually ensures that all processors on the ring agree on a direction, regardless of the initial states of the processors on which the protocol is started. In this paper we present two uniform deterministic self-stabilizing ring-orientation protocols for rings with an odd number of processors using only a constant number of states per processor. The first protocol operates in the link-register model under the distributed daemon, and the second protocol operates in the state-reading model under the central daemon. Both protocols do not assume an upper bound on the length of the ring and are therefore applicable to dynamic rings. As an application of our techniques we are able to prove that under the central daemon on an odd-length ring, the link-register model and the state-reading model are equivalent in the sense that any self-stabilizing protocol for the one model can be transformed to an equivalent, self-stabilizing protocol in the other model