Published by MIT Press. Copyright 1996 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

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 On^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 On^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.

• Preformatted versions of the article
  • DVI (135,148 bytes)
  • PostScript (356,681 bytes)
  • PDF (331,273 bytes)
  • Audio by AsTeR (to appear)
• Executable code suppplement discussed in the article
  • readme.txt (1,407 bytes)
  • Makefile (56 bytes)
  • explore.c (8,652 bytes)
  • explore.h (2,117 bytes)
  • problem.c (15,443 bytes)
  • problem.h (1,422 bytes)
  • explore.out (2,193 bytes)
• Source materials for custom formatting
  • LaTeX (cj96-05.tex, 96,180 bytes)
  • BIBTeX (cj96-05.bib, 9,287 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 164 bytes)
  • Macro redefinitions for custom formatting (cjrdefs.tex, 419 bytes)
  • Self citation in BIBTeX (311 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.1996.005

---

Article 4 Article 6
Volume 1996 Published articles

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