Self-Stabilizing Small k-Dominating Sets

Abstract

A self-stabilizing algorithm, after transient faults hit the system and place it in some arbitrary global state, causes the system to recover in finite time without external (e.g., human) intervention. In this paper, we give a distributed asynchronous silent self-stabilizing algorithm for finding a minimal k-dominating set of at most ⌈n/(k+1)⌉ processes in an arbitrary identified network of size n. We give a transformer that allows our algorithm to work under an unfair daemon, the weakest scheduling assumption. The complexity of our solution is O(n) rounds and O(Dn³) steps using O(logk + logn + klogN/k) bits per process, where D is the diameter of the network and N is an upper bound on n.