A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem

We give a silent self-stabilizing algorithm for the generalized minimal k-dominating set problem in a connected distributed network G. Given a positive integer k and two sets of processes R ⁎ ⊆ D ⁎ , the problem is to find a set D which is minimal subject to the conditions that R ⁎ ⊆ D ⊆ D ⁎ and that D is k-dominating relative to D ⁎ , meaning that every process within distance k of D ⁎ is also within distance k of D. The algorithm is order-invariant, requires O ( log ⁡ N + log ⁡ k ) space per process, works under the distributed unfair scheduler, and converges in O ( N + k ) rounds, where N is a given upper bound on the number of processes.