
doi: 10.1007/bfb0020439
The 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 is an adaption of a randomized protocol presented by Israeli and Jalfon [IJ93], and operates in the link-register model under the distributed daemon. The second protocol operates in the state-reading model under the central daemon, and complements the impossibility results proven in [IJ93]. Applying our results 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 a self-stabilizing protocol for the one model can be transformed to an equivalent protocol in the other model.
Shared memory, Communication, Orientation, Rings, Symmetry breaking, Synchronization, Self-Stabilization
Shared memory, Communication, Orientation, Rings, Symmetry breaking, Synchronization, Self-Stabilization
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
