全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Self-Stabilizing Small k-Dominating Sets

Keywords: Distributed systems , self-stabilization , k-dominating sets , k-clustering

Full-Text   Cite this paper   Add to My Lib

Abstract:

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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133