Abstract FR:

Un algorithme reparti est un algorithme qui s'execute sur plusieurs sites distincts (sans controle centralise, ni memoire commune). Un algorithme reparti est auto-stabilisant si, apres une corruption de ses memoires et en l'absence de nouvelles corruptions, il passe d'abord par une phase de stabilisation (ou son comportement peut etre errone) avant de revenir a une phase stabilisee (ou son comportement est normal). Plus precisement, un algorithme est dit auto-stabilisant si, quelle que soit la configuration initiale de ses memoires et en l'absence de panne, il converge fatalement vers un comportement correct. Cette these definit un modele formel et precis pour les algorithmes repartis qui s'adapte particulierement bien a la propriete d'auto-stabilisation. Ce modele est ensuite utilise pour definir formellement la propriete d'auto-stabilisation et pour classer les algorithmes repartis relativement a leurs capacites a acquerir la propriete d'auto-stabilisation de maniere efficace et par des procedes automatiques. Dans une seconde partie, le modele est utilise pour prouver trois algorithmes auto-stabilisants originaux d'exclusion mutuelle et de k-exclusion mutuelle (deux d'entre eux sont probabilistes). Cette partie d'application de l'auto-stabilisation au probleme de l'exclusion mutuelle est motivee par le fait que tout algorithme qui resoud ce probleme apparait dans le classement prealable comme impropre a acquerir efficacement la propriete d'auto-stabilisation par un procede automatique