-
Views
-
Cite
Cite
Hisaki Kobayashi, Yuichi Sudo, Hirotsugu Kakugawa, Toshimitsu Masuzawa, A Self-Stabilizing Distributed Algorithm for the Generalized Dominating Set Problem With Safe Convergence, The Computer Journal, Volume 66, Issue 6, June 2023, Pages 1452–1476, https://doi.org/10.1093/comjnl/bxac021
Close - Share Icon Share
Abstract
A self-stabilizing distributed algorithm is guaranteed eventually to reach and stay at a legitimate configuration regardless of the initial configuration of a distributed system. In this paper, we propose the generalized dominating set problem, which is a generalization of the dominating set and |$k$|-redundant dominating set problems. In the generalized dominating set we propose in this paper, each node |$P_{i}$| is given its set of domination wish sets, and a generalized dominating set is a set of nodes such that each node is contained in the set or has a wish set in which all its members are in the set. We propose a self-stabilizing distributed algorithm for finding a minimal generalized dominating set in an arbitrary network under the unfair distributed daemon. The proposed algorithm converges in |$O(n^{3}m)$| steps and |$O(n)$| rounds, where |$n$| (resp., |$m$|) is the number of nodes (resp., edges). Furthermore, it has the safe convergence property with safe convergence time in |$O(1)$| rounds. The space complexity of the proposed algorithm is |$O(\Delta \log n)$| bits per node, where |$\Delta $| is the maximum degree of nodes.
