Verimag

Technical Reports

Datta, Ajoy K. and Devismes, Stéphane and Heurtefeux, Karel and Larmore, Lawrence L. and Rivierre, Yvan
Self-Stabilizing Small k-Dominating Sets (2011)

TR-2011-6.pdf


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

Abstract: 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 the ceiling of n/(k+1) processes in an arbitrary identified network of size n. Using a transformer also proposed in this paper, we make our algorithm working under an unfair daemon (the weakest scheduling assumption). The complexity of our solution is in O(n) rounds and O(D n n) steps using O(log(n) + k log(n/k)) bits per process where D is the diameter of the network.

Contact | Plan du site | Site réalisé avec SPIP 3.0.26 + AHUNTSIC [CC License]

info visites 874732