SELF-STABILIZING GRAPH PROTOCOLS
Abstract
We provide self-stabilizing algorithms to obtain and maintain a maximal matching, maximal independent set or minimal dominating set in a given system graph. They converge in linear rounds under a distributed or synchronous daemon. They can be implemented in an ad hoc network by piggy-backing on the beacon messages that nodes already use.
References
- IEEE/ACM Transactions on Networking 4, 902 (1996), DOI: 10.1109/90.556356. Crossref, ISI, Google Scholar
-
H. Attiya and J. Welch , Distributed Computing: Fundamentals. Simulations and Advanced Topics ( McGraw Hill , 1998 ) . Google Scholar -
T. W. Haynes , S. T. Hedetniemi and P. J. Slater , Fundamentals of Domination in Graphs ,Monographs and Textbooks in Pure and Applied Mathematics 208 ( Marcel Dekker Inc , New York , 1998 ) . Google Scholar S. Fujita , T. Kameda and M. Yamashita , A resource assignment problem on graphs, Proceedings of the 6th International Symposium on Algorithms and Computation (1995) pp. 418–427. Google Scholar- Communications of the Association of the Computing Machinery 17, 643 (1974). Crossref, ISI, Google Scholar
-
S. Dolev , Self-Stabilization ( MIT Press , 2000 ) . Crossref, Google Scholar - Information Processing Letters 43, 77 (1992), DOI: 10.1016/0020-0190(92)90015-N. Crossref, ISI, Google Scholar
S. K. Shukla , D. J. Rosenkrantz and S. S. Ravi , Observations on self-stabilizing graph algorithms for anonymous networks, Proceedings of the Second Workshop on Self-Stabilizing Systems (1995) pp. 7.1–7.15. Google ScholarY. Afek and S. Dolev , Local stabilizer, Proceedings of the 5th Israeli Symposium on Theonj of Computing and Systems (1997) pp. 74–84. Google ScholarJ. Beauquier , Self-stabilizing local mutual exclusion and daemon refinement, DISC00 Distributed Computing 14th International Symposium,LNCS (Springer, 2000) pp. 223–237. Google Scholar- Int. J. Found. Comput. Set. 16, 19 (2005), DOI: 10.1142/S012905410500284X. Link, ISI, Google Scholar
S. Shukla , D. Rosenkrantz and S. Ravi , Developing self-stabilizing coloring algorithms via systematic randomization, Proceedings of the International Workshop on Parallel Processing (1994) pp. 668–673. Google ScholarW. Goddard , Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks, Proceedings of 5th IPDPS Workshop on Advances in Parallel and Distributed Computational Models (Nice, 2003) p. 162. Google ScholarZ. Xu , A synchronous selfstabilizing minimal domination protocol in an arbitrary network graph, Distributed Computing — IWDC 2003, 5th International Workshop,LNCS (Springer, 2003) pp. 26–32. Google ScholarM. Ikeda , S. Kamei and H. Kakugawa , A space-optimal self-stabilizing algorithm for the maximal independent set problem, PDCAT Proc. 3rd Int. Conf. Parallel and Distributed Computing, Applications and Technologies (2002) pp. 70–74. Google Scholar


