Construction auto-stabilisante d'un arbre couvrant de poids minimum

Résumé : L'arbre couvrant de poids minimum offre une solution de routage ayant le double avantage de donner une structure de communication simple et économique. Dans ce papier, nous présentons un nouvel algorithme auto-stabilisant pour la construction d'un arbre couvrant de poids minimum dans un système distribué et asynchrone. Notre solution améliore l'existant en permettant d'atteindre un meilleur compromis entre le temps de convergence, $O(n^2)$, et la complexité en mémoire nécessaire sur chaque noeud du réseau, $O(\log^2 n)$. Le temps de convergence est amélioré d'un facteur multiplicatif $\Theta(n)$ au prix d'un facteur multiplicatif de $O(\log n)$ sur la mémoire. La clé de voûte de ce travail est l'utilisation d'une méthode de nommage auto-stabilisante permettant d'identifier pour toute paire de noeuds le plus proche ancêtre commun dans l'arbre.
Type de document :
Communication dans un congrès
Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2011, Cap Estérel, France. 2011
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00587591
Contributeur : Stephane Rovedakis <>
Soumis le : mercredi 20 avril 2011 - 23:05:24
Dernière modification le : mardi 17 avril 2018 - 11:32:11
Document(s) archivé(s) le : jeudi 21 juillet 2011 - 02:51:38

Fichier

SS_MST_Dyn.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00587591, version 1

Collections

Citation

Lélia Blin, Shlomi Dolev, Maria Potop-Butucaru, Stephane Rovedakis. Construction auto-stabilisante d'un arbre couvrant de poids minimum. Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2011, Cap Estérel, France. 2011. 〈inria-00587591〉

Partager

Métriques

Consultations de la notice

334

Téléchargements de fichiers

163