CJTCS Volume 1996 Article 5

Uniform Self-Stabilizing Orientation of Unicyclic networks under Read/Write Atomicity

H. James Hoover (University of Alberta) and Piotr Rudnicki (University of Alberta)
5 December 1996
Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors
Abstract

A distributed system is self-stabilizing if its behavior is correct regardless of its initial state. A ring is a distributed system in which all processors are connected in a cycle and each processor communicates directly with only its two neighbors. A ring is oriented when all processors have a consistent notion of their left and right neighbors. A ring is uniform when all processors run the same program and have no distinguishing attributes, such as processor IDs. A well-known self-stabilizing uniform protocol for ring orientation is that of [Israeli, Jalfon]. For a ring of size n , this protocol will stabilize in expected O n ^2 processor activations. This assumes that processors are scheduled by a distributed demon ---one in which the communication registers between processors can be atomically updated (a read followed by a write), and the processors have the ability to make random choices.

This paper generalizes the notion of orienting a ring to that of orienting a unicyclic network, that is, a ring with trees attached. We present a very simple protocol for the self-stabilizing orientation of such unicyclic networks. It has the same expected O n ^2 processor activation performance as the Israeli and Jalfon protocol for rings. But ours works under the more general scheduling assumption of a read/write demon ---one in which a read or write of a communication register is atomic, but an update (a read followed by a write) is not. We similarly assume the ability to make random choices. A subresult of our protocol is a uniform self-stabilizing algorithm for the two processor token-passing problem under the read/write demon.

Our protocol is uniform in the sense that all processors of the same degree are identical. In addition, observations of the behavior of the protocol on an edge yield no information about the degree of the processors at the ends of the edge.

[] Article 4 [] Article 6
[back] Volume 1996 [back] Published articles
[CJCTS home]

Last modified: Tue Nov 25 10:55:41 CST