A linear-time self-stabilizing distributed algorithm for the minimal minus ($L, K, Z$) -domination problem under the distance-2 model
A linear-time self-stabilizing distributed algorithm for the minimal minus ($L, K, Z$) -domination problem under the distance-2 model
复制标题
距离2模型下最小负($L,K,Z$)支配问题的线性时间自稳定分布式算法
DOI：
10.1109/candarw57323.2022.00018
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kamei Sayaka
中科院分区：
文献类型：
--
作者：
Kakugawa Hirotsugu;Kamei Sayaka
图的支配问题是图的基本问题之一，有许多不同的变体。该问题在分布式环境下具有实际应用价值，在分布式计算领域得到了较好的研究。在这篇文章中，我们提出了一个新的问题，称为负()-控制问题，其中，和是满足，和的整数。负()控制问题是为图中的每个顶点赋值，使得值的局部和大于或等于的问题。因为它和负控制问题是相同的，所以它是负控制问题的推广。然后，我们针对负()-支配问题提出了一种自稳定分布式算法，其中自稳定是一类容错的分布式算法，可以容忍任意有限个瞬时故障。该算法是在距离-2模型和不公平中心守护进程下设计的，其收敛时间与进程数呈线性关系。如果将其转化为带变压器的普通距离-1模型，我们得到一个算法，其收敛时间为。
The domination problem is one of the fundamental graph problems and there are many variations. The problem has practical applications in a distributed setting, and studied well in the distributed computing community. In this paper, we propose a new problem called the minus () -domination problem where, andare integers such that, and. The minus () -domination problem is a problem to assign a valuefor each vertex in a graph such that the local summation of values is greater than or equal to. Because it is the same as the minus domination problem whenand, it is an extension of the minus domination problem. Then, we propose a self-stabilizing distributed algorithm for the minus () -domination problem, where self-stabilization is a class of fault-tolerant distributed algorithms that tolerate arbitrary finite number of transient faults. The proposed algorithm is designed under the distance-2 model and the unfair central daemon, and its convergence time is, that is, linear to, whereis the number of processes. If it is converted into the ordinary distance-1 model with a transformer, we obtain an algorithm whose convergence time is.