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.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00587591
Contributor : Stephane Rovedakis <>
Submitted on : Wednesday, April 20, 2011 - 11:05:24 PM
Last modification on : Monday, July 22, 2019 - 11:38:09 AM
Long-term archiving on : Thursday, July 21, 2011 - 2:51:38 AM

File

SS_MST_Dyn.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00587591, version 1

Citation

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

Share

Metrics

Record views

390

Files downloads

206