Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We propose a general self-stabilizing scheme for solving any synchronization problem whose safety specification can be defined using a local property. We demonstrate the versatility of our scheme by showing that very memory-efficient solutions to many well-known problems (e.g., asynchronous phase clock, local mutual exclusion, local reader-writers, and local group mutual exclusion) can be derived using the proposed framework. We show that all these algorithms use a phase clock whose minimum size in terms of number of states per process is equal to CG + TG - 1, where CG is the length of the maximal cycle of the shortest maximum cycle basis if the graph contains cycles and 2 (otherwise) for tree networks, and TG is the length of the longest chordless cycle (i.e., hole) if the graph contains cycles and 2 for tree networks. In particular, for the asynchronous phase clock problem, our solution significantly improves all existing self-stabilizing solutions---all of them require quadratic space in terms of the number of states.As a by-product of our scheme, we present a silent bounded algorithm which can be used to transform any serial system into a distributed one. Thus, it answers an open question in [16], if there exists a bounded system transformation which is silent.

REFERENCES

• 1: A. Arora , M. Gouda, Distributed Reset, IEEE Transactions on Computers, v.43 n.9, p.1026-1038, September 1994 [doi>10.1109/12.312126]
• 2: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 3: Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, Time optimal self-stabilizing synchronization, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.652-661, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167256]
• 4: Joffroy Beauquier , Ajoy Kumar Datta , Maria Gradinariu , Frederic Magniette, Self-Stabilizing Local Mutual Exclusion and Daemon Refinement, Proceedings of the 14th International Conference on Distributed Computing, p.223-237, October 04-06, 2000
• 5: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 6: C Boulinier, S Cantarell, F Petit, and V Villain. A note on a self-stabilizing local mutual exclusion algorithm. Technical Report RR03-02, LaRIA, University of Picardie Jules Verne, 2003.
• 7: C Boulinier, F Petit, and V Villain. About bounded self-stabilizing local mutual exclusion algorithms. Technical Report RR04-02, LaRIA, University of Picardie Jules Verne, 2004.
• 8: S Cantarell. Group Mutual Exclusion and Self-Stabilization. PhD thesis, LRI, Université de Paris-Sud, Orsay, France, 2003.
• 9: David M. Chickering , Dan Geiger , David Heckerman, On finding a cycle basis with a shortest maximal cycle, Information Processing Letters, v.54 n.1, p.55-58, April 14, 1995 [doi>10.1016/0020-0190(94)00231-M]
• 10: Alain Cournier , Ajoy K. Datta , Franck Petit , Vincent Villain, Snap-Stabilizing PIF Algorithm in Arbitrary Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.199, July 02-05, 2002
• 11: P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
• 12: JM Couvreur, N Francez, and M Gouda. Asynchronous unison. In Proceedings of the 12th IEEE International Conference on Distributed Computing Systems (ICDCS'92), pages 486--493, 1992.
• 13: 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]
• 14: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 15: Shlomi Dolev , Mohamed G. Gouda , Marco Schneider, Memory requirements for silent stabilization, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.27-34, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248055]
• 16: Mohamed G. Gouda , F. Furman Haddix, The alternator, Workshop on Self-stabilizing Systems, p.48-53, June 05, 1999
• 17: Yuh-Jzer Joung, Asynchronous group mutual exclusion (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.51-60, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277706]
• 18: Hirotsugu Kakugawa , Masafumi Yamashita, Self-Stabilizing Local Mutual Exclusion on Networks in which Process Identifiers are not Distinct, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.202, October 13-16, 2002
• 19: Mikhail Nesterenko , Anish Arora, Stabilization-preserving atomicity refinement, Journal of Parallel and Distributed Computing, v.62 n.5, p.766-791, May 2002 [doi>10.1006/jpdc.2001.1828]
• 20: G. Varghese, SELF-STABILIZATION BY LOCAL CHECKING AND CORRECTION, Massachusetts Institute of Technology, Cambridge, MA, 1992

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Performance, Theory

Keywords:
asynchronous unison, local (group) mutual exclusion, self-stabilization, synchronization