Self-Stabilizing Global Optimization Algorithms for Large Network Graphs

References

• Estrin , D. , Govindan , R. , Heidemann , J. S. and Kumar , S. 1999 . “ Next century challenges: Scalable coordination in sensor networks ” . In Mobile Computing and Networking 263 – 270 .
   Google Scholar
• Dijkstra , E. W. 1974 . “Self-stabilizing systems in spite of distributed control” . Communications of the ACM , 17 : 643 – 644 .
   Web of Science ®Google Scholar
• 3.L. Lamport, “Solved problems, unsolved problems, and non-problems in concurrency,” in Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing, 1–11, 1984
   Google Scholar
• Schneider , M. 1993 . Self-stabilization . ACM Computing Surveys , 25 ( 1 ) March : 45 – 67 . [CROSSREF]
   Web of Science ®Google Scholar
• Herman. T., “A comprehensive bibliograph on self-stabilization, a working paper,” Chicago J. Theoretical Comput. Sci. http://www.cs.uiowa.edu/ftp/selfstab/bibliography
   Google Scholar
• 6. C. Boulinier, F. Petit, and V. Villain, “When graph theory helps self-stabilization,” in Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (PODC 2004, St. John's), 150–159, 2004
   Google Scholar
• Attiya , H. and Welch , J. 1998 . Distributed Computing: Fundamentals, Simulations and Advanced Topics , McGraw Hill .
   Google Scholar
• Haynes , T. W. , Hedetniemi , S. T. and Slater , P. J. 1998 . Fundamentals of Domination in Graphs , New York : Marcel Dekker .
   Google Scholar
• Fujita , S. , Kameda , T. and Yamashita , M. 1995 . A resource assignment problem on graphs . Proceedings of the 6th International Symposium on Algorithms and Computation . December 1995 , Cairns, Australia. pp. 418 – 427 .
   Google Scholar
• Dai , F. and Wu , J. 2004 . An extended localized algorithm for connected dominating set formation in ad hoc wireless networks . IEEE Trans. Parallel Distrib. Syst. , 15 ( 10 ) : 908 – 920 . [CROSSREF]
   Web of Science ®Google Scholar
• 11. D. Peleg, “Distributed data structures: A complexity oriented view,” in Proceedings of the Fourth International Workshop on Distributed Algorithms, 71–89, 1990
   Google Scholar
• Goddard , W. , Hedetniemi , S. T. , Jacobs , D. P. and Srimani , P. K. 2003 . A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph . Proceedings of the 8thIPDPS Workshop on Formal Methods for Parallel Programming . April 2003 , Nice, France.
   Google Scholar
• Karaata , M. H. 2001 . Self-stabilizing strong fairness under weak fairness . IEEE Transactions on Parallel and Distributed Systems , 12 ( 4 ) : 337 – 345 . [CROSSREF]
   Google Scholar
• 14. S. C. Hsu and S. T. Huang, “Analyzing self-stabilization with finite-state machine model,” in Proceedings of the 12th International Conference on Distributed Computing Systems, 624–631, 1992
   Google Scholar
• Hedetniemi , S. T. , Jacobs , D. P. and Srimani , P. K. 2001 . Maximal matching stabilizes in time o(m) . Information Processing Letters , 80 ( 5 ) : 221 – 223 . [CROSSREF]
   Google Scholar
• 16. W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, “The b-matching paper,” Preprint
   Google Scholar
• Dolev , S. 2000 . Self-Stabilization , MIT Press .
   Google Scholar
• 18. J. Beauquier, M. Gradinariu, and C. Johnen, “Cross-over composition — enforcement of fairness under unfair adversary,” in WSS01 Proceedings of the Fifth International Workshop on Self-Stabilizing Systems, Springer LNCS, 2194, 19–34, 2001
   Google Scholar
• Nesterenko , M. and Arora , A. 2002 . Stabilization-preserving atomicity refinement . Journal of Parallel and Distributed Computing , 62 ( 5 ) : 766 – 791 . [CROSSREF]
   Google Scholar
• 20. S. K. Shukla, D. J. Rosenkrantz, and S. S. Ravi, “Observations on self-stabilizing graph algorithms for anonymous networks,” in Proceedings of the Second Workshop on Self-Stabilizing Systems, 7.1–7.15, 1995
   Google Scholar
• Blair , J. R. S. and Manne , F. 2003 . Efficient self-stabilizing algorithms for tree networks . Proceedings of ICDCS-2003 . 2003 , Island.
   Google Scholar
• Hedetniemi , S. T. , Pokrass Jacobs , D. and Srimani , P. K. 2001 . Maximal matching stabilizes in time O(m) . Information Processing Letters , 80 : 221 – 223 . [CROSSREF]
   Google Scholar
• 23.W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, “Fault tolerant algorithms for orderings and colorings,” in 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 2004
   Google Scholar
• Hedetniemi , S. M. , Hedetniemi , S. T. , Jacobs , D. P. and Srimani , P. K. 2003 . Self-stabilizing algorithms for minimal dominating sets and independent sets . Computers & Mathematics with Applications , 46 : 5 – 6 . [INFOTRIEVE] [CSA]
   Google Scholar
• Haynes , T. W. , Hedetniem , S. T. and Slater , P. J. 1998 . “ Fundamentals of domination in graphs ” . In Monographs and Textbooks in Pure and Applied Mathematics , New York : Marcel Dekker .
   Google Scholar
• Kutter , S. and Peleg , D. 1998 . Fast distributed construction of small k-dominations sets and applications . Journal of Algorithms , 28 : 40 – 66 . [CSA] [CROSSREF]
   Google Scholar
• Gupta , S. K. S. and Srimani , P. K. Self-stabilizing multicast protocols for ad hoc networks . Journal of Parallel and Distributed Computing , 63 ( 1 ) 87 – 96 . [CSA] [CROSSREF]
   Google Scholar
• 28.M. Gairing, Goddard, W. Hedetniemi, S. T. and P. Kristiansen, “Distance-two information in self-stabilizing algorithms,” To appear in Parallel Processing Letters, 2005.
   Google Scholar
• 29. W. Goddard, T. St. Hedetniemi, D. P. Jacobs, and P. K. Srimani, “Self-stabilizing distributed algorithm for strong matching in a system graph,” Springer-Verlag Lecture Notes in Computer Science 2913, December, 2003
   Google Scholar