Self-stabilizing Algorithms for {k}-domination
In the self-stabilizing algorithmic paradigm for distributed
computing each node has only a local view of the system, yet in a -
nite amount of time the system converges to a global state, satisfying
some desired property. A function f : V (G) ! f0; 1; 2; : : : ; kg is a fkg-
dominating function if j2N[i]f(j) k for all i 2 V (G). In this paper we
present self-stabilizing algorithms for nding a minimal fkg-dominating
function in an arbitrary graph. Our rst algorithm covers the general
case, where k is arbitrary. This algorithm requires an exponential num-
ber of moves, however we believe that its scheme is interesting on its
own, because it can insure that when a node moves, its neighbors hold
correct values in their variables. For the case that k = 2 we propose a
linear time self-stabilizing algorithm.