UNIFORM SELF-STABILIZING ORIENTATION OF UNICYCLIC NETWORKS UNDER READWRITE ATOMICITY/

A distributed system is self-stabilizing if its behavior is correct re gardless of its initial state. A ring is a distributed system in which all processors are connected in a cycle and each processor communicat es directly with only its two neighbors. A ring is oriented when all p rocessors 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-s tabilizing uniform protocol for ring orientation is that of [IJ93b]. F or 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 pr ocessors can be atomically updated (a, read followed by a write), and the processors have the ability to make random choices. This paper gen eralizes the notion of orienting a ring to that of orienting a unicycl ic network, that is, a ring with trees attached. We present a very sim ple protocol for the self-stabilizing orientation of such unicyclic ne tworks. It has the same expected O(n(2)) processor activation performa nce as the Israeli and Jalfon protocol for rings. But ours works under the more general scheduling assumption of a read/write demon-one in w hich a read or write of a communication register is atomic, but an upd ate (a read followed by a write) is not. We similarly assume the abili ty to make random choices. A subresult of our protocol is a uniform se lf-stabilizing algorithm for the two processor token-passing problem u nder the read/write demon. Our protocol is uniform in the sense that a ll processors of the same degree are identical. In addition, observati ons of the behavior of the protocol on an edge yield no information ab out the degree of the processors at the ends of the edge.