Résumé | Un système distribué est dit auto-stabilisant s’il peut reprendre un comportement correct en un temps fini après l’occurrence de fautes et ce sans intervention extérieure. De ce fait, l’auto-stabilisation est une approche optimiste pour la tolérance aux fautes dans le sens où elle protège le système des fautes transitoires. Un algorithme auto-stabilisant peut être défini selon différents modèles de communication ainsi que différents modèles de calcul. En effet, prouver la convergence d'un algorithme auto-stabilisant se doit dêtre faite selon un démon/scheduler qui peut être centralisé ou distribué, équitable ou non. De de plus, la complexité de ces algorithmes peut se calculer selon différentes mesures : moves, steps ou rounds, chacune d'entre elles apportant une connaissance propre sur l'algorithme proposé. Cependant, réussir à borner l'ensemble de ces mesures n'est pas toujours trivial, en particulier pour les cas les plus généraux de démons. La littérature des algorithmes auto-stabilisants est très riches. Cependant, nous allons nous intéresser dans cet exposé aux algorithmes auto-stabilisants pour quelques paramètres de théorie des graphes. En particulier, nous nous focaliserons dans un premier temps sur des décompositions particulières des graphes : en triangles et en étoiles uniformes ainsi que des paramètres de domination. Nous nous attarderons par la suite sur les techniques de preuve de convergence utilisées pour ces algorithmes. |