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, 10:00 - 18 June 2013, 12:00
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
Programming computing media (reporté)
Combinatorics
Friday 18 September 2020 - 14:30
Salle : 445 - PCRI-N
Frédéric Gruau .............................................

forum-dev Continuous Integration
Friday 05 June 2020 - 10:00
Salle : 0 - 650
Erik Bray .............................................

Large-scale Spectral Clustering for GPU-based Plat
High-performance computing
Tuesday 24 March 2020 - 10:30
Salle : 465 - PCRI-N
Guanlin He .............................................

Recherche Opérationnelle à Google
Stochastic Combinatorial Optimization
Thursday 12 March 2020 - 14:30
Salle : 445 - PCRI-N
Laurent Perron .............................................

Forum dev-LRI
Wednesday 05 February 2020 - 14:00
Salle : 455 - PCRI-N
Erik Bray .............................................