Previous [ 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 (November 2008)

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
+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, Dijkstras central demon model, distributed system, legitimate configuration

Full Text () Retrieve PDF document (200811_06.pdf)

Received February 26, 2007; revised September 4, 2007; accepted October 18, 2007.
Communicated by Chin-Laung Lei.