Self-stabilizing population protocols

ABSTRACT

This article studies self-stabilization in networks of anonymous, asynchronously interacting nodes where the size of the network is unknown. Constant-space protocols are given for Dijkstra-style round-robin token circulation, leader election in rings, two-hop coloring in degree-bounded graphs, and establishing consistent global orientation in an undirected ring. A protocol to construct a spanning tree in regular graphs using O(log D) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.

REFERENCES

• 1: Angluin, D., Aspnes, J., Chan, M., Fischer, M. J., Jiang, H., and Peralta, R. 2005. Stably computable properties of network graphs. In Proceedings of the Distributed Computing in Sensor Systems: 1st IEEE International Conference On Distributed (DCOSS'05). V. K. Prasanna, S. Iyengar, P. Spirakis, and M. Welsh, Eds. Lecture Notes in Computer Science, vol. 3560. Springer-Verlag, Berlin, Germany, 63--74.
• 2: Dana Angluin , James Aspnes , Zoë Diamadi , Michael J. Fischer , René Peralta, Computation in networks of passively mobile finite-state sensors, Distributed Computing, v.18 n.4, p.235-253, March 2006 [doi>10.1007/s00446-005-0138-3]
• 3: Angluin, D., Aspnes, J., Eisenstat, D., and Ruppert, E. 2007. The computational power of population protocols. Distrib. Comput. 20, 4, 279--304.
• 4: Hagit Attiya , Amotz Bar-Noy , Danny Dolev , Daphne Koller , David Peleg , Radiger Reischuk, Achievable cases in an asynchronous environment, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), p.337-346, October 12-14, 1987 [doi>10.1109/SFCS.1987.5]
• 5: Joffroy Beauquier , Maria Gradinariu , Colette Johnen, Memory space requirements for self-stabilizing leader election protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.199-207, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301358]
• 6: 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]
• 7: Shlomi Dolev , Amos Israeli , Shlomo Moran, Uniform Dynamic Self-Stabilizing Leader Election, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.424-440, April 1997 [doi>10.1109/71.588622]
• 8: Mohamed G. Gouda , F. Furman Haddix, The stabilizing token ring in three bits, Journal of Parallel and Distributed Computing, v.35 n.1, p.43-48, May 25, 1996 [doi>10.1006/jpdc.1996.0066]
• 9: Maria Gradinariu , Colette Johnen, Self-stabilizing Neighborhood Unique Naming under Unfair Scheduler, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.458-465, August 28-31, 2001
• 10: Jerrold R. Griggs , Roger K. Yeh, Labelling graphs with a condition at distance 2, SIAM Journal on Discrete Mathematics, v.5 n.4, p.586-595, Nov. 1992 [doi>10.1137/0405048]
• 11: 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]
• 12: Herman, T. and Tixeuil, S. 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks. Lecture Notes in Computer Science, vol. 3121, Springer, Berlin, Germany. 45--58.
• 13: Higham, L. and Myers, S. 1999. Self-stabilizing token circulation on anonymous message passing rings. Tech. Rep., University of Calgary.
• 14: G. Itkis , L. Levin, Fast and lean self-stabilizing asynchronous protocols, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.226-239, November 20-22, 1994 [doi>10.1109/SFCS.1994.365691]
• 15: Gene Itkis , Chengdian Lin , Janos Simon, Deterministic, Constant Space, Self-Stabilizing Leader Election on Uniform Rings, Proceedings of the 9th International Workshop on Distributed Algorithms, p.288-302, September 13-15, 1995
• 16: Johnen, C. 2004. Bounded service time and memory space optimal self-stabilizing token circulation protocol on unidirectional rings. In Procedings of the 18th International Parallel and Distributed Processing Symposium. IEEE Computer Society, Los Alamitos, CA.
• 17: Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129777]
• 18: Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073977]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

General Terms:
Algorithms, Reliability

Keywords:
Anonymous, fairness, finite-state, population protocols, self-stabilization, sensor networks