Journal Title International Journal of Networking and Computing Journal Abbreviation ijnc Publisher Group University of Hiroshima (HU) Website http://www.ijnc.org/index.php/ijnc

PDF (201 kb)

Title	Self-Stabilizing Small k-Dominating Sets
Authors	Datta, Ajoy K.; Larmore, Lawrence L.; Devismes, Stéphane; Heurtefeux, Karel; Rivierre, Yvan
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.
Publisher	International Journal of Networking and Computing
Date	2013-01-21
Source	2185-2839

 

See other article in the same Issue