A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon

作者：Chiu Well Y; Chen Chiuyuan^*; Tsai Shih Yu

来源：Information Processing Letters, 2014, 114(10): 515-518.

DOI：10.1016/j.ipl.2014.04.011

• Self-stabilizing algorithm
• Fault tolerance
• Distributed computing
• Graph algorithm
• Domination

A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [9]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm.

• 出版日期2014-10