Light enabling snap-stabilization of fundamental protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Light enabling snap-stabilization of fundamental protocols

Full text

Pdf (208 KB)

Source

ACM Transactions on Autonomous and Adaptive Systems (TAAS) archive
Volume 4 , Issue 1 (January 2009) table of contents

Article No. 6

Year of Publication: 2009

ISSN:1556-4665

Authors

Alain Cournier	LaRIA CNRS, Amiens, France
Stephane Devismes	LaRIA CNRS, Amiens, France
Vincent Villain	LaRIA CNRS, Amiens, France

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 67, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1462187.1462193 What is a DOI?

ABSTRACT

In this article, we show that some fundamental self- and snap-stabilizing wave protocols (e.g., token circulation, PIF, etc.) implicitly assume a very light property that we call BreakingIn. We prove that BreakingIn is strictly induced by self- and snap-stabilization. Combined with a transformer, BreakingIn allows to easily turn the non-fault-tolerant versions of those protocols into snap-stabilizing versions. Unlike the previous solutions, the transformed protocols are very efficient and work at least with the same daemon as the initial versions extended to satisfy BreakingIn. Finally, we show how to use an additional property of the transformer to design snap-stabilizing extensions of those fundamental protocols like Mutual Exclusion.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baruch Awerbuch , Robert G. Gallager, Distributed BFS algorithms, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.250-256, October 21-23, 1985 [doi>10.1109/SFCS.1985.20]
	2	Alain Bui , Ajoy Kumar Datta , Franck Petit , Vincent Villain, State-optimal snap-stabilizing PIF in tree networks, Workshop on Self-stabilizing Systems, p.78-85, June 05, 1999
	3	Alain Cournier , Ajoy K. Datta , Franck Petit , Vincent Villain, Enabling Snap-Stabilization, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.12, May 19-22, 2003
	4	Cournier, A., Devismes, S., Petit, F., and Villain, V. 2004. Snap-stabilizing depth-first search on arbitrary networks. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'04). Lecture Notes in Computer Science, vol. 3544, 267--282.
	5	Alain Cournier , Stéphane Devismes , Franck Petit , Vincent Villain, Snap-Stabilizing Depth-First Search on Arbitrary Networks, The Computer Journal, v.49 n.3, p.268-280, May 2006 [doi>10.1093/comjnl/bxh154]
	6	Cournier, A., Devismes, S., and Villain, V. 2005. A snap-stabilizing DFS with a lower space requirement. In Proceedings of the 7th International Symposium on Self-Stabilizing Systems (SSS'05). Lecture Notes in Computer Science, vol. 3764, 33--47.
	7	Cournier, A., Devismes, S., and Villain, V. 2006a. From self- to snap- stabilization. In Proceedings of the 8th International Symposium on Self-Stabilization, Safety, and Security (SSS'06). Lecture Notes in Computer Science, vol. 4280, 199--213.
	8	Alain Cournier , Stephane Devismes , Vincent Villain, Snap-Stabilizing PIF and Useless Computations, Proceedings of the 12th International Conference on Parallel and Distributed Systems, p.39-48, July 12-15, 2006 [doi>10.1109/ICPADS.2006.100]
	9	Cournier, A., Devismes, S., and Villain, V. 2007. Light enabling snap-stabilization. Tech. rep. 2007-04, LaRIA, CNRS FRE 2733.
	10	Delaët, S., Ducourthial, B., and Tixeuil, S. 2005. Self-stabilization with r-operators revisited. In Self-Stabilizing Systems, T. Herman and S. Tixeuil, Eds. Lecture Notes in Computer Science, vol. 3764, 68--80.
	11	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]
	12	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]
	13	Dolev, S. and Tzachar, N. 2006. Empire of colonies: Self-stabilizing and self-organizing distributed algorithms. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS). Number 4305 in Lecture Notes in Computer Science. Springer, 230--243.
	14	Shing-Tsaan Huang , Nian-Shing Chen, Self-stabilizing depth-first token circulation on networks, Distributed Computing, v.7 n.1, p.61-66, November 1993 [doi>10.1007/BF02278857]
	15	Shing-Tsaan Huang , Nian-Shing Chen, A self-stabilizing algorithm for constructing breadth-first trees, Information Processing Letters, v.41 n.2, p.109-117, Feb. 14, 1992 [doi>10.1016/0020-0190(92)90264-V]
	16	Colette Johnen, Memory efficient, self-stabilizing algorithm to construct BFS spanning trees, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.288, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259508]
	17	Johnen, C., Alima, L., Datta, A. K., and Tixeuil, S. 2002. Optimal snap-stabilizing neighborhood synchronizer in tree networks. Parall. Proc. Lett. 12, 3-4, 327--340.
	18	Shmuel Katz , Kenneth J. Perry, Self-stabilizing extensions for message-passing systems, Distributed Computing, v.7 n.1, p.17-26, November 1993 [doi>10.1007/BF02278852]
	19	Gerard Tel, Introduction to Distributed Algorithms, Cambridge University Press, New York, NY, 2001
	20	Villain, V. 2002. Snap-stabilization versus self-stabilization. Proceedings of the Journées Internationales sur l'auto-Stabilisation. CIRM, Luminy France.