Self-stabilizing symmetry breaking in constant-space (extended abstract)

ABSTRACT

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic (coin-flipping) finite state machine which sends and receives messages. We show that the solution to this problem is equivalent to symmetry breaking (i.e., leader election). Requiring only constant-size messages and message-passing model has practical implications: our solution can be implemented in high-speed networks using a universal fast hardware switches (i.e., finite state machines) of size independent of the size of the network.

REFERENCES

• AAHK86: Karl Abrahamson , Andrew Adler , Lisa Higham , David Kirkpatrick, Probabilistic solitude verification on a ring, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.161-173, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10604]
• AB89: Y. AFEK AND G.M. BROWN, Self-stabilization over unreliable communication media, manuscript. (Previous version appeared as: Self-stabilization of the alternating-bit protocol, Proc. 8th IEEE Syrup. on Reliable Distrgbuted Systems (1989), 10-12.
• AKY90: Yehuda Afek , Shay Kutten , Moti Yung, Memory-efficient self stabilizing protocols for general networks, Proceedings of the 4th international workshop on Distributed algorithms, p.15-28, June 1991, Bari, Italy
• AN90: N. ALON AND M. NAOR, Coin-flipping games immune against linear-sized coalition, Proc. 31st IEEE Syrup. on Foundatsons of Computer Science (1990), 46-54.
• Ang80: 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]
• ASW85: Chagit Attiya , Marc Snir , Manfred Warmuth, Computing on an anonymous ring, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.196-203, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323614]
• APV91: Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
• AV91: Baruch Awerbuch , George Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.258-267, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185377]
• BGW89: 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]
• BP88: J. E. Burns , Jan K. Pachl, Uniform self-stabilizing rings, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• BCK+83: W. Bux, F.H. CLOSe, K. KOMMZRLE, H.J. KELLER AND H.R. MOLLER, Architecture and design of a reliable tokenring network, IEEE J. on Selected Areas sn Comm., 1(5), (1983), 756-765.
• CV86: R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
• CO90: I. CIDON AND Y. OF#, MetaRing - A full-duplex ring with fairness and spatial reuse, Proc INFOCOM'90 969-981. (Also: Accepted to IEEE Tras. on Comm.).
• Dij74: 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]
• DIM91: Shlomi Dolev , Amos Israeli , Shlomo Moran, Resource bounds for self stabilizing message driven protocols, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.281-293, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112624]
• FL84: Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987 [doi>10.1145/7531.7919]
• FS86: G N Frederickson , N Santoro, Breaking symmetry in synchronous networks, Proc. of the Aegean workshop on computing on VLSI algorithms and architectures, p.26-33, August 1986, Loutraki, Greece
• Her90: T. Herman, Probabilistic self-stabilization, Information Processing Letters, v.35 n.2, p.63-67, June 1990 [doi>10.1016/0020-0190(90)90107-9]
• HN88: A. Hopper , R. M. Needham, The Cambridge Fast Ring Networking System, IEEE Transactions on Computers, v.37 n.10, p.1214-1223, October 1988 [doi>10.1109/12.5983]
• IJ90a: Amos Israeli , Marc Jalfon, Token management schemes and random walks yield self-stabilizing mutual exclusion, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.119-131, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93409]
• IJ90b: Amos Israeli , Marc Jalfon, Self-stabilizing ring orientation, Proceedings of the 4th international workshop on Distributed algorithms, p.1-14, June 1991, Bari, Italy
• IR81: A. ITAI AND M RODEH, Symmetry breaking in distributive networks, Proc. #nd IEEE Syrup. on Foundatsons of Computer Science (1981), 150-159.
• It90: Alon Itai, On the computational power needed to elect a leader (extended abstract), Proceedings of the 4th international workshop on Distributed algorithms, p.29-39, June 1991, Bari, Italy
• KP90: Shmuel Katz , Kenneth Perry, Self-stabilizing extensions for message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.91-101, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93405]
• LTG90: A.A. LAZAR, A. T. TZMPL# AND R. GIDRON, MAGNET Ih A metropolitan area network based on asynchronous time sharing, IEEE J. on Selected Areas in Comm., 8(8), (1990), 1582-1594.
• LL90: Leslie Lamport , Nancy Lynch, Distributed computing: models and methods, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• MZ86: Y Mansour , S Zaks, On the bit complexity of distributed computations in a ring with a leader, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.151-160, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10603]
• Mis83: Jayadev Misra, Detecting termination of distributed computations using markers, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.290-294, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806729]
• OMS89: H. OHmSm, N. MORITA, AND S. Suzum, ATM ring protocol and performance, Proc. ICC'89, 13.1, (1989), 394-398
• OY90: Yoram Ofek , Moti Yung, Principle for high speed network control: congestion-and deadlock-freeness, self-routing, and a single buffer per link, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.161-175, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93414]
• PKR82: Jan K. Pachl , E. Korach , D. Rotem, A technique for proving lower bounds for distributed maximum-finding algorithms (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.378-382, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802213]
• R86: F.E. Ross, FDDI - a Tutorial, IBEE Commumcatson Magazine, 24(5), (1986), 10-17.
• RL81: Daniel Lehmann , Michael O. Rabin, On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-138, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567547]
• SS89: B. Schieber, Calling names in nameless networks, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.319-328, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73004]
• STT89: Paul G. Spirakis , Basil Tampakas , Athanasios Tsiolis, Symmetry Breaking in Asynchronous Rings with O(n) Messages, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.233-241, September 26-28, 1989
• V84: Paul M.B. Vitányi, Distributed elections in an archimedean ring of processors, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.542-547, December 1984 [doi>10.1145/800057.808725]

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

  G. Mathematics of Computing

General Terms:
Design, Theory