International Parallel and Distributed Processing Symposium (IPDPS'03)
A Self-Stabilizing Distributed Algorithm for Minimal Total Domination in an Arbitrary System Graph
Nice, France
April 22-April 26
ISBN: 0-7695-1926-1
In a graph G = (V,E) a set S \subseteq V is said to be total dominating if every v \in V is adjacent to some member of S. When the graph represents a communication network, a total dominating set corresponds to a collection of servers having a certain desirable backup property, namely, that every server is adjacent to some other server. Self-stabilization, introduced by Dijkstra, is the most inclusive approach to fault tolerance in distributed systems. We propose a new self-stabilizing distributed algorithm for finding a minimal total dominating set in an arbitrary graph. We also show how the basic ideas behind the proposed protocol can be generalized to solve other related problems.
Citation:
Wayne Goddard, Stephen T. Hedetniemi, David P. Jacobs, Pradip K Srimani, "A Self-Stabilizing Distributed Algorithm for Minimal Total Domination in an Arbitrary System Graph," ipdps, pp.240b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003