Self-Stabilizing Global Optimization Algorithms for Large Network Graphs

Abstract

The paradigm of self-stabilization provides a mechanism to design efficient localized distributed algorithms that are proving to be essential for modern day large networks of sensors. We provide self-stabilizing algorithms (in the shared-variable ID-based model) for three graph optimization problems: a minimal total dominating set (where every node must be adjacent to a node in the set) and its generalizations, a maximal k-packing (a set of nodes where every pair of nodes are more than distance k apart), and a maximal strong matching (a collection of totally disjoint edges).

†This work has been supported by NSF grant # ANI-0218495.

Keywords:

• Self-stabilization
• Optimization Alogrithms
• k-packing

Notes

†This work has been supported by NSF grant # ANI-0218495.

¹A preliminary version of the total domination algorithm was presented in [12]

²A preliminary version was presented in [29]

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

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

11. D. Peleg, “Distributed data structures: A complexity oriented view,” in Proceedings of the Fourth International Workshop on Distributed Algorithms, 71–89, 1990

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

16. W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, “The b-matching paper,” Preprint

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

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

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

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.

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