A Self-Stabilizing Algorithm for Finding a Minimal Distance-2 Dominating Set in Distributed Systems
Ji-Cherng Lin, Tetz C. Huang, Cheng-Pin Wang, Chih‐Yuan Chen · 2008
The study of various dominating set problems is an important area within graph theory. In applications, a dominating set in a system can be considered as an ideal place for allocating resources. And, a minimal dominating set allows allocating a smaller number of resources. Distance-versions of the concept of minimal dominating sets are more applicable to modeling real-world problems, such as placing a smaller number of objects within acceptable distances of a given population. However, due to the main restriction that any processor in a distributed system can only access the data of its direct neighbors, a self-stabilizing algorithm for finding a minimal distance-k (with k ≥ 2) dominating set is hard to get, and its correctness is hard to verify. In this paper, a self-stabilizing algorithm for finding a minimal distance-2 dominating set is proposed. The algorithm can be applied to any distributed system that operates under the central demon model. The correctness of the algorithm is verified.