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
Demographic reconstruction from paleogenomes of th
Thursday 25 February 2021 - 14h00
Salle : 435 - PCRI-N
Nina Marchi .............................................

A Graph-based Similarity Approach to Classify Recu
Thursday 18 February 2021 - 14h00
Salle : 435 - PCRI-N
Coline Gianfrotta .............................................

"Answer Set Programming for computing constraints-
Thursday 04 February 2021 - 14h00
Salle : 435 - PCRI-N
Maxime Mahout .............................................

"Pandæsim: An Epidemic Spreading Stochastic Simula
Thursday 14 January 2021 - 14h00
Salle : 435 - PCRI-N
Patrick Amar .............................................

Disentangling the role of selection on the evoluti
Friday 02 October 2020 - 17h30
Salle : 455 - PCRI-N
Fanny Pouyet .............................................