Self-stabilizing philosophers with generic conflicts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Self-stabilizing philosophers with generic conflicts

Full text

Pdf (310 KB)

Source

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

Article No. 7

Year of Publication: 2009

ISSN:1556-4665

Authors

Praveen Danturi	Kent State University
Mikhail Nesterenko	Kent State University
Sébastien Tixeuil	Université Pierre et Marie Curie

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 121, 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.1462194 What is a DOI?

ABSTRACT

We generalize the classic dining philosophers problem to separate the conflict and communication neighbors of each process. Communication neighbors may directly exchange information while conflict neighbors compete for the access to the exclusive critical section of code. This generalization is motivated by a number of practical problems in distributed systems including problems in wireless sensor networks. We present a self-stabilizing deterministic algorithm—GDP that solves this generalized problem. Our algorithm is terminating. We formally prove GDP correct and evaluate its performance. We extend the algorithm to handle a similarly generalized drinking philosophers and the committee coordination problem. We describe how GDP can be implemented in wireless sensor networks and demonstrate that this implementation does not jeopardize its correctness or termination properties.

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	Gheorghe Antonoiu , Pradip K. Srimani , Jan Van den Bussche, A self-stabilizing distributed algorithm to find the median of a tree graph, Journal of Computer and System Sciences, v.58 n.1, p.215-221, Feb. 1999 [doi>10.1006/jcss.1998.1606]
	2	Anish Arora , Mikhail Nesterenko, Unifying stabilization and termination in message-passing systems, Distributed Computing, v.17 n.3, p.279-290, March 2005 [doi>10.1007/s00446-004-0111-6]
	3	Arumugam, M. and Kulkarni, S. 2005. Self-stabilizing deterministic TDMA for sensor networks. Tech. rep. MSU-CSE-05-19, Michigan State University.
	4	Banerjee, S., Kommareddy, C., Kar, K., Bhattacharjee, S., and Khuller, S. 2003. Construction of an efficient overlay multicast infrastructure for real-time applications. In Proceedings of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1521--1531.
	5	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
	6	Blin, L., Cournier, A., and Villain, V. 2003. An improved snap-stabilizing PIF algorithm. In Proceedings of the 6th International Symposium on Self-Stabilizing Systems, (SSS03), S.-T. Huang and T. Herman, Eds. Lecture Notes in Computer Science, vol. 2704. Springer, 199--214.
	7	Christian Boulinier , Franck Petit , Vincent Villain, When graph theory helps self-stabilization, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011790]
	8	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
	9	Cantarell, S., Datta, A., and Petit, F. 2003. Self-stabilizing atomicity refinement allowing neighborhood concurrency. In Proceedings of the 6th International Symposium on Self-Stabilizing Systems. Lecture Notes in Computer Science, vol. 2704. Springer, 102--112.
	10	K. M. Chandy , J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.632-646, Oct. 1984 [doi>10.1145/1780.1804]
	11	K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	12	Ajoy K. Datta , Maria Gradinariu , Michel Raynal, Stabilizing mobile philosophers, Information Processing Letters, v.95 n.1, p.299-306, 16 July 2005 [doi>10.1016/j.ipl.2005.03.006]
	13	Dijkstra, E. 1968. Cooperating Sequential Processes. Academic Press.
	14	Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
	15	Gairing, M., Goddard, W., Hedetniemi, S., Kristiansen, P., and McRae, A. 2004. Distance-two information in self-stabilizing algorithms. Parall. Process. Lett. 14, 3-4, 387--398.
	16	Goddard, W., Hedetniemi, S., Jacobs, D., and Trevisan, V. 2006. Distance-K information in self-stabilizing algorithms. In Proceedings of the 13th Colloquium on Structural Information and Communication Complexity (SIROCCO), 349--356.
	17	Mohamed G. Gouda, Elements of network protocol design, John Wiley & Sons, Inc., New York, NY, 1998
	18	Mohamed G. Gouda , F. Furman Haddix, The alternator, Workshop on Self-stabilizing Systems, p.48-53, June 05, 1999
	19	Mohamed G. Gouda , Nicholas J. Multari, Stabilizing Communication Protocols, IEEE Transactions on Computers, v.40 n.4, p.448-458, April 1991 [doi>10.1109/12.88464]
	20	Maria Gradinariu , Sebastien Tixeuil, Conflict Managers for Self-stabilization without Fairness Assumption, Proceedings of the 27th International Conference on Distributed Computing Systems, p.46, June 25-27, 2007 [doi>10.1109/ICDCS.2007.95]
	21	Ted Richard Herman, Adaptivity through distributed convergence, University of Texas at Austin, Austin, TX, 1992
	22	Herman, T. and Tixeuil, S. 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 45--58.
	23	Hoover, H. 1995. On the self-stabilization of processors with continuous states. In Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 8.1--8.15.
	24	Shing-Tsaan Huang, The Fuzzy Philosophers, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.130-136, May 01-05, 2000
	25	Prasad Jayanti, Adaptive and efficient abortable mutual exclusion, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.295-304, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872079]
	26	Johnen, C., Alima, L., Datta, A., and Tixeuil, S. 2002. Optimal snap-stabilizing neighborhood synchronizer in tree networks. Parall. Process. Lett. 12, 3-4, 327--340.
	27	Kulkarni, S. and Arumugam, M. 2003. Collision-free communication in sensor networks. In Proceedings of the Symposium on Self-Stabilizing Systems (SSS). Lecture Notes in Computer Science, vol. 2704, 17--31.
	28	Nancy A. Lynch, Fast allocation of nearby resources in a distributed system, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.70-81, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804654]
	29	N. Malhotra , M. Krasniewski , C. Yang , S. Bagchi , W. Chappell, Location Estimation in Ad Hoc Networks with Directional Antennas, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.633-642, June 06-10, 2005 [doi>10.1109/ICDCS.2005.47]
	30	N. Mitton , E. Fleury , I. Guerin Lassous , B. Sericola , S. Tixeuil, Fast Convergence in Self-Stabilizing Wireless Networks, Proceedings of the 12th International Conference on Parallel and Distributed Systems, p.31-38, July 12-15, 2006 [doi>10.1109/ICPADS.2006.47]
	31	Mitton, N., Paroux, K., Sericola, B., and Tixeuil, S. 2008. Ascending runs in dependent uniformly distributed random variables: Application to wireless networks. Methodology and Computing in Applied Probability.
	32	Masaaki Mizuno , Mikhail Nesterenko, A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments, Information Processing Letters, v.66 n.6, p.285-290, June 30, 1998 [doi>10.1016/S0020-0190(98)00069-6]
	33	Nesterenko, M. and Arora, A. 2001. Self-stabilizing routing in wireless embedded. In Proceedings of the SRDS Workshop on Reliability in Embedded Systems, 16--22.
	34	Mikhail Nesterenko , Anish Arora, Dining Philosophers that Tolerate Malicious Crashes, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.191, July 02-05, 2002
	35	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]
	36	Michael L. Scott , William N. Scherer, Scalable queue-based spin locks with timeout, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.44-52, June 2001, Snowbird, Utah, United States
	37	Shi, S. and Turner, J. S. 2002. Routing in overlay multicast networks. In Proceedings of the IEEE INFOCOM. Vol. 3. IEEE Computer Society, 1200--1208.
	38	Sivilotti, P., Pike, S., and Sridhar, N. 2000. A new distributed resource-allocation algorithm with optimal failure locality. In Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems. Vol. 2. IASTED/ACTA Press, 524--529.