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

Lawrence Larmore, University of Nevada, Las Vegas
Ajoy Datta, University of Nevada, Las Vegas
Stéphane Université de Bordeaux, Université Grenoble Alpes

Abstract

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 + logk) 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.