ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 31/8-10 - 2012  - pp.1273-1299  - doi:10.3166/tsi.31.1273-1299
TITRE
Algorithme autostabilisant construisant un petit ensemble k-dominant

TITLE
A self-stabilizing algorithm for building a small k-dominating set

RÉSUMÉ

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(Dn3) 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.



ABSTRACT

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(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.



AUTEUR(S)
Ajoy K. DATTA, Stéphane DEVISMES, Karel HEURTEFEUX, Lawrence L. LARMORE, Yvan RIVIERRE

MOTS-CLÉS
autostabilisation, ensemble k-dominant, systèmes distribués.

KEYWORDS
self-stabilization, k-dominating set, distributed systems.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (246 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier