|
 
|
[CRV12] Le premier algorithme stabilisant de construction d'arbre totalement polynomial
Conférence Nationale avec comité de lecture : 14ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2012, pp.1-4,
motcle:
Résumé:
Un algorithme stabilisant $A$ est dit \emph{totalement polynomial} s'il existe deux constantes $a$ et $b$ tel que pour tout réseau $\cal{R}$ (de diamètre $d$ comportant $n$ noeuds), la complexité de notre algorithme $A$ appartient à $O(d^a)$ rondes et $O(n^b)$ pas de calcul.
La construction d'un arbre couvrant est un problème fondamental des systèmes distribués. L'utilisation d'un arbre couvrant permet de résoudre plus efficacement d'autres problèmes comme le routage, l'exclusion mutuelle ou la réinitialisation d'un réseau. La stabilisation est une technique générale et flexible permettant de traiter les fautes transitoires qui peuvent survenir dans un réseau.
Or les solutions existantes résolvent ce problème soit avec un nombre de pas de calcul exponentiel soit avec un nombre de rondes fonction de la taille du réseau. Ces caractéristiques les rendent inappropriées dans le cadre du passage à l'échelle.
Nous proposons le premier algorithme stabilisant totalement polynomial permettant de construire un arbre couvrant en largeur ayant une complexité en rondes de $O(d^2)$ et en pas de calcul de $O(n^6)$. Le diamètre est généralement inférieur à la taille du réseau ($\log(n)$ en moyenne). Ainsi, cet algorithme atteint le meilleur compromis entre les complexités en rondes et en pas de calcul.
Equipe:
mim
Collaboration:
Laboratoire MIS
BibTeX
| @inproceedings { | |||
| CRV12, | |||
| title | = | "{Le premier algorithme stabilisant de construction d'arbre totalement polynomial}", | |
| author | = | " A. Cournier and S. Rovedakis and V. Villain ", | |
| booktitle | = | "{14ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)}", | |
| year | = | 2012, | |
| month | = | "May", | |
| pages | = | "1-4", | |
| } | |||
