Uniform self-stabilizing rings

ABSTRACT

A self-stabilizing system has the property that, no matter how it is perturbed, it eventually returns to a legitimate configuration. Dijkstra originally introduced the self-stabilization problem and gave several solutions for a ring of processors in his 1974 Communications of the ACM paper. His solutions use a distinguished processor in the ring, which effectively acts as a controlling element to drive the system toward stability. Dijkstra has observed that a distinguished processor is essential if the number of processors in the ring is composite. We show, by presenting a protocol and proving its correctness, that there is a self-stabilizing system with no distinguished processor if the size of the ring is prime. The basic protocol uses &THgr; (n2) states in each processor when n is the size of the ring. We modify the basic protocol to obtain one that uses &THgr; (n2/ln n) states.

REFERENCES

• 1: Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
• 2: Geoffrey M. Brown , Mohamed G. Gouda , Chuan-Lin Wu, Token Systems That Self-Stabilize, IEEE Transactions on Computers, v.38 n.6, p.845-852, June 1989 [doi>10.1109/12.24293]
• 3: BURNS, J. E. Symmetry in systems of asynchronous processes. In Proceedings of the 22nd Symposium on Foundations of Computer Science (Nashville, Tenn., Oct. 1981). IEEE, New York, 1981, pp. 169-174.
• 4: BURNS, J.E. Self-stabilizing rings without demons. Tech. Rep. GIT-ICS-87/36, Georgia Institute of Technology, Atlanta, Ga., Nov. 1987.
• 5: BURNS, J. E., GOUDA, M. G., AND MILLER, a.E. On relaxing interleaving assumptions. Tech. Rep. GIT-ICS-88/29, Georgia Institute of Technology, Atlanta, Ga., Aug. 1988.
• 6: Ernest J. H. Chang , Gaston H. Gonnet , Doron Rotem, On the costs of self-stabilization, Information Processing Letters, v.24 n.5, p.311-316, 16 March 1987 [doi>10.1016/0020-0190(87)90155-4]
• 7: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 8: DIJKSTRA, E. W. Self-stabilization in spite of distributed control (EWD391). Reprinted in Selected Writing on Computing: A Personal Perspective. Springer-Verlag, Berlin, 1982, pp. 41-46.
• 9: Edsger W. Dijkstra, A belated proof of self-stabilization, Distributed Computing, v.1 n.1, p.5-6, Jan. 1986 [doi>10.1007/BF01843566]
• 10: Ramsey W. Haddad , Donald E. Knuth, A Programming and Problem-Solving Seminar, Stanford University, Stanford, CA, 1985
• 11: Ralph E. Johnson , Fred B. Schneider, Symmetry and similarity in distributed systems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.13-22, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323598]
• 12: KRUIJER, H. S.M. Self-stabilization (in spite of distributed control) in tree-structured systems. Inf. Process. Lett. 8, 2 (1979), 91-95.
• 13: Leslie Lamport, 1983 Invited address solved problems, unsolved problems and non-problems in concurrency, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.1-11, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806731]
• 14: SEGER, C.-J. Private communication, Oct. 1986.{
• 15: TCHUENTE, M. Sur l'auto-stabilisation dans un r~seau d'ordinateurs. RA1RO Inf. Theor. 15 (1981), 47-66.
• 16: WHITBY-STREVENS, C. On the performance of Dijkstra's self-stabilising algorithms in spite of distributed control. Univ. of Warwick Computer Centre, Tech. Rep. No. 21, Warwick, England, Mar. 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Token rings

General Terms:
Design, Reliability, Theory