World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on High-Level Parallel Programming and ApplicationsNo Access

SELF-STABILIZING GRAPH PROTOCOLS

    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

    • H. Abu-Amaraet al., IEEE/ACM Transactions on Networking 4, 902 (1996), DOI: 10.1109/90.556356. Crossref, ISIGoogle 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
    • E. W. Dijkstra, Communications of the Association of the Computing Machinery 17, 643 (1974). Crossref, ISIGoogle Scholar
    • S.   Dolev , Self-Stabilization ( MIT Press , 2000 ) . CrossrefGoogle Scholar
    • S. C. Hsu and S. T. Huang, Information Processing Letters 43, 77 (1992), DOI: 10.1016/0020-0190(92)90015-N. Crossref, ISIGoogle 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 Scholar
    • Y. Afek and S. Dolev, Local stabilizer, Proceedings of the 5th Israeli Symposium on Theonj of Computing and Systems (1997) pp. 74–84. Google Scholar
    • J. Beauquieret al., Self-stabilizing local mutual exclusion and daemon refinement, DISC00 Distributed Computing 14th International Symposium, LNCS (Springer, 2000) pp. 223–237. Google Scholar
    • W. Goddardet al., Int. J. Found. Comput. Set. 16, 19 (2005), DOI: 10.1142/S012905410500284X. Link, ISIGoogle 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 Scholar
    • W. Goddardet al., 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 Scholar
    • Z. Xuet al., 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 Scholar
    • M. 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