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).
EstrinD.GovindanR.HeidemannJ. S., and KumarS., “Next century challenges: Scalable coordination in sensor networks,” in Mobile Computing and Networking, 263–270, 1999.
2.
DijkstraE. W., “Self-stabilizing systems in spite of distributed control,”Communications of the ACM, 17, 643–644, 1974.
3.
LamportL., “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.
BoulinierC.PetitF., and VillainV., “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.
7.
AttiyaH., and WelchJ., Distributed computing: fundamentals, simulations, and advanced topics.Mc Graw Hill, 1998.
8.
HaynesT. W.HedetniemiS. T., and SlaterP. J., Fundamentals of domination in graphs.New York: Marcel Dekker, 1998.
9.
FujitaS.KamedaT., and YamashitaM., “A resource assignment problem on graphs,”Proceedings of the 6th International Symposium on Algorithms and Computation, (Cairns, Australia) 418–427, December, 1995.
10.
DaiF., and WuJ., “An extended localized algorithm for connected dominating set formation in ad hoc wireless networks,”IEEE Trans. Parallel Distrib. Syst., 15, 10, 908–920, 2004.
11.
PelegD., “Distributed data structures: A complexity oriented view,” in Proceedings of the Fourth International Workshop on Distributed Algorithms, 71–89, 1990.
12.
GoddardW.HedetniemiS. T.JacobsD. P., and SrimaniP. K., “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, (Nice, France), April, 2003.
13.
KaraataM. H., “Self-stabilizing strong fairness under weak fairness,”IEEE Transactions on Parallel and Distributed Systems, 12, 4, 337–345, 2001.
14.
HsuS. C. and HuangS. T., “Analyzing self-stabilization with finite-state machine model,” in Proceedings of the 12th International Conference on Distributed Computing Systems, 624–631, 1992.
15.
HedetniemiS. T.JacobsD. P., and SrimaniP. K., “Maximal matching stabilizes in time o(m),”Information Processing Letters, 80, 5, 221–223, 2001.
16.
GoddardW.HedetniemiS. T.JacobsD. P., and SrimaniP. K., “The b-matching paper,” Preprint.
17.
DolevS., Self-Stabilization.MIT Press, 2000.
18.
BeauquierJ.GradinariuM., and JohnenC., “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.
19.
NesterenkoM., and AroraA., “Stabilization-preserving atomicity refinement,”Journal of Parallel and Distributed Computing, 62, 5, 766–791, 2002.
20.
ShuklaS. K.RosenkrantzD. J., and RaviS. S., “Observations on self-stabilizing graph algorithms for anonymous networks,” in Proceedings of the Second Workshop on Self-Stabilizing Systems, 7.1–7.15, 1995.
21.
BlairJ. R. S. and ManneF., “Efficient self-stabilizing algorithms for tree networks,” in Proceedings of ICDCS-2003, Island, 2003.
22.
HedetniemiS. T.JacobsD. Pokrass, and SrimaniP. K., “Maximal matching stabilizes in time O(m).”Information Processing Letters, 80, 221–223, 2001.
23.
GoddardW.HedetniemiS. T.JacobsD. P., and SrimaniP. K., “Fault tolerant algorithms for orderings and colorings,” in 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 2004.
24.
HedetniemiS. M.HedetniemiS. T.JacobsD. P.SrimaniP. K., “Self-stabilizing algorithms for minimal dominating sets and independent sets,”Computers & Mathematics with Applications46, 5–6, 2003.
25.
HaynesT. W.HedetniemS. T.SlaterP. J., “Fundamentals of domination in graphs,”Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker: New York, 1998.
26.
KutterS., and PelegD., “Fast distributed construction of small k-dominations sets and applications,”Journal of Algorithms, 28, 40–66, 1998.
27.
GuptaS. K. S.SrimaniP. K., “Self-stabilizing multicast protocols for ad hoc networks,”Journal of Parallel and Distributed Computing, 63, 1, 87–96, 2003.
28.
GairingM.GoddardW.HedetniemiS. T. and KristiansenP., “Distance-two information in self-stabilizing algorithms,” To appear in Parallel Processing Letters, 2005.
29.
GoddardW.St. HedetniemiT.JacobsD. P., and SrimaniP. K., “Self-stabilizing distributed algorithm for strong matching in a system graph,”Springer-Verlag Lecture Notes in Computer Science 2913, December, 2003.
