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).