A self-stabilizing algorithm for the distributed minimal k-redundant dominating set problem in tree networks

Self-stabilization is a theoretical framework of nonmasking fault-tolerant distributed algorithms. We investigate self-stabilizing distributed solutions to the minimal k-redundant dominating set (MRDS) problem in tree networks. The MRDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G=(V,E), a set M⊆V is a k-redundant dominating set of G if and only if each vertex not in M is adjacent to at least k vertices in M. We propose a self-stabilizing distributed algorithm that solves the MRDS problem for anonymous tree networks.