Self-Stabilizing Small k-Dominating Sets
Self-Stabilizing Small k-Dominating Sets
复制标题
自稳定小型 k 支配集
DOI：
10.1109/icnc.2011.15
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Yvan Rivierre
中科院分区：
文献类型：
--
作者：
A. Datta;L. Larmore;Stéphane Devismes;K. Heurtefeux;Yvan Rivierre
一种自稳定算法，在瞬时故障击中系统并将其置于某个任意全局状态之后，在有限时间内恢复，而无需外部（例如，人）干预。本文提出了一个分布式异步静默自稳定算法，用于在任意确定的网络中寻找至多n/（k+1）个进程的最小k-控制集。我们提出了一个Transformer，它允许我们的算法在不公平的守护进程（最弱的调度假设）下工作。我们的解决方案的复杂度是O（n）轮和O（Dn ²）步，每个进程使用O（log n + k log n）位，其中D是网络的直径。
A self-stabilizing algorithm, after transient faults hit the system and place it in some arbitrary global state, recovers in finite time without external (e.g., human) intervention. In this paper, we propose a distributed asynchronous silent self-stabilizing algorithm for finding a minimal k-dominating set of at most n/(k+1) processes in an arbitrary identified network of size n. We propose a transformer that allows our algorithm work under an unfair daemon (the weakest scheduling assumption). The complexity of our solution is in O(n) rounds and O(D n²) steps using O(log n + k log n) bits per process where D is the diameter of the network.