Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Algorithme de Renversement de Liens : convergence et complexité
Bernadette Charron-Bost

18 June 2013, 10h00 - 18 June 2013, 12h00
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :
Les algorithmes de Renversement de Liens (LR) constituent un schéma algorithmique distribué de base en particulier pour les réseaux mobiles ad-hoc. Ce schéma a été proposé à l'origine par Gafni et Bertsekas en 1981 pour le routage et a été par la suite utilisé pour l'élection de leader, l'exclusion mutuelle ou encore l'allocation de ressources. Les deux algorithmes LR les plus populaires sont l'algorithme Full Reversal (FR) et l'algorithme Partial Reversal (PR).

Nous proposons tout d'abord une version unifiée de tous les algorithmes LR et donnons une preuve générale de convergence de ces algorithmes. En particulier, nous donnons la première preuve de convergence de l'algorithme Partial Reversal. A partir de cette version unifiée, nous calculons exactement la complexité en travail de chaque algorithme LR alors que seule la complexité en travail de Full Reversal était connue jusqu'à présent.

Pour la complexité en temps, seules des bornes étaient connues dans le cas de l'algorithme Full Reversal. En montrant que le comportement de l'algorithme Full Reversal correspond en fait à un système dynamique linéaire dès lors que l'on travaille dans l'algèbre min-plus, nous établissons une expression exacte de la complexité en temps de Full Reversal. Une réduction générale au cas Full Reversal permet ensuite de calculer la complexité en temps de chaque algorithme LR.

A l'aide d'outils élémentaires de théorie des jeux, nous menons une étude comparative des différents algorithmes LR. En particulier, nous montrons que vis à vis de la complexité en travail l'algorithme Partial Reversal est meilleur que l'algorithme Full Reversal alors que vis à vis de la complexité en temps, les conclusions sont inverses.

Travail en collaboration avec M. Fuegger (TU, Wien), J. Welch (Texas A&M University) et J. Widder (TU, Wien).

Pour en savoir plus :
Séminaires
Quantum at LRI
Calcul quantique
Tuesday 04 February 2020 - 09h00
Salle : 465 - PCRI-N
.............................................

Progressive Data Analysis: a new computation parad
Gestion de données du Web
Friday 24 January 2020 - 14h00
Salle : 435 - PCRI-N
Jean-Daniel Fekete .............................................

Jeux d’instructions : des extensions SIMD aux exte
Architectures parallèles
Tuesday 21 January 2020 - 10h30
Salle : 465 - PCRI-N
Daniel Etiemble .............................................

Forum dev-LRI
Tuesday 14 January 2020 - 14h00
Salle : 445 - PCRI-N
Erik Bray .............................................

La transformation du travail, un analyseur des tra
Wednesday 18 December 2019 - 10h00
Salle : 475 - PCRI-N
Raquel Becerril-Ortega .............................................