JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]


Journal of Information Science and Engineering, Vol. 24 No. 6, pp. 1709-1718


A Self-Stabilizing Algorithm for Finding a Minimal Distance-2 Dominating Set in Distributed Systems


Ji-Cherng Lin, Tetz C. Huang, Cheng-Pin Wang and Chih-Yuan Chen+
Department of Computer Science and Engineering 
Yuan Ze University 
Chungli, 320 Taiwan 
E-mail: csjclin@saturn.yzu.edu.tw 
+Department of Computer Science and Information Engineering 
Nanya Institute of Technology 
Chungli, 320 Taiwan


    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.


Keywords: minimal distance-2 dominating set, self-stabilizing algorithm, Dijkstra’s central demon model, distributed system, legitimate configuration

  Retrieve PDF document (JISE_200806_06.pdf)