Algorithme autostabilisant construisant un petit ensemble k-dominant

摘要

We propose a distributed asynchronous silent self-stabilizing algorithm for finding a minimal k-dominating set in an arbitrary identified network of n processes. The size of the computed k-dominating set is at most [n/(k+1)] processes. 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(Dn~3) 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.%Nous proposons un algorithme distribué, asynchrone, silencieux et autostabilisant calculant un ensemble k-dominant minimal d'un réseau identifié quelconque de n processus. La taille de l'ensemble k-dominant calculé est d'au plus [n/(k+1)] processus. à partir d'un transformateur présenté également dans cet article, nous obtenons une solution fonctionnant sous un ordonnanceur inéquitable (le plus général des ordonnanceurs). Notre solution stabilise en O(n) rondes et O(Dn~3) pas de calcul, où D est le diamètre du réseau. Enfin, elle nécessite O(log k + log n + k log N/k ) bits de mémoire par processus où N est un majorant de n.