文章基本信息

标题：Self-Stabilizing Small k-Dominating Sets
其他标题：Self-Stabilizing Small k-Dominating Sets
本地全文：下载
作者：Ajoy K. Datta ; Lawrence L. Larmore ; StÃ©phane Devismes 等
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2013
卷号：3
期号：1
页码：116-136
语种：English
出版社：International Journal of Networking and Computing
摘要：A self-stabilizing algorithm, after transient faults hit the system and place it in some arbitrary global state, causes the system to recover in finite time without external (e.g., human) intervention. In this paper, we give 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 give a transformer that allows our algorithm to work under an unfair daemon, the weakest scheduling assumption. The complexity of our solution is O(n) rounds and O(Dn3) steps using O(logk + logn + klogN/k) bits per process, where D is the diameter of the network and N is an upper bound on n.
关键词：Distributed systems; self-stabilization; k-dominating sets; k-clustering