[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
International Journal of Networking and Computing
Online ISSN : 2185-2847
Print ISSN : 2185-2839
ISSN-L : 2185-2839
Regular Papers
Self-Stabilizing Small k-Dominating Sets
Ajoy K. DattaLawrence L. LarmoreStéphane DevismesKarel HeurtefeuxYvan Rivierre
Author information
JOURNAL FREE ACCESS

2013 Volume 3 Issue 1 Pages 116-136

Details
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(log k + log n + k log N/k) bits per process, where D is the diameter of the network and N is an upper bound on n.

Content from these authors
© 2013 International Journal of Networking and Computing
Previous article Next article
feedback
Top