{'fraction_non_alphanumeric': 0.02912621359223301, 'fraction_numerical': 0.0, 'mean_word_length': 5.034146341463415, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Game-Theoretic Approach to Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Sets

Dominating set is a subset of nodes called dominators in a graph such that every non-dominator nodes (called dominatee) is adjacent to at least one dominator. This paper considers a more general multi-dominating problem where each node i, dominator or dominatee, is required to have at least ki neighboring dominators, and different node can have different ki value. We first propose a game design toward this problem. This game is self-stabilizing (i.e., it always ends up with a legitimate state regardless of its initial configuration). The obtained result is guaranteed minimal (i.e., it contains no proper subset that is also a multi-dominating set) and Pareto optimal (we cannot increase the payoff of some player without sacrificing the payoff of any other). We then point out challenges when turning the design into a distributed algorithm using guarded commands. We present an algorithm that is proved weakly stabilizing. Simulation results show that the proposed game and algorithm produce smaller dominating sets, k-dominating sets, and multi-dominating sets in various network topologies when compared with prior approaches.