Résumé | La notion d'auto-stabilisation a été introduite par Edsger
Dijkstra en 1974 : Quel que soit son état initial, un système
auto-stabilisant est certain d'atteindre un état cohérent en un
nombre fini d'étapes. Une telle propriété est hautement
souhaitable, car après une perturbation inattendue de l'état des
mémoires des processus, un système auto-stabilisant retourne
finalement à un état correct sans aucune intervention extérieure.
Les deux principaux problèmes "étalons" de l'algorithmique
répartie sont l'élection de leader et l'exclusion mutuelle. Je me
suis intéressée à concevoir des solutions auto-stabilisantes à
ces problèmes dans le cadre d'anneaux anonymes. Dans la plupart
des cas, il n'existe pas d'algorithme déterministe et
auto-stabilisant d'élection de leader, ni d'exclusion
mutuelle. J'ai donc proposé des algorithmes probabilistes. Je me
suis particulièrement attachée, à concevoir des solutions
optimales en terme d'espace mémoire. |