Mardi 15 décembre : Soutenance de thèse de Khaled Mohamed, équipe SDMA, à 14h00, en salle des thèses de l’EDSS.
L'auto-stabilisation dans les systèmes distribués est un concept introduit par Dijkstra en 1974. Ce concept s'est avéré être le plus efficace pour faire face aux pannes transitoires.
Ces pannes apparaissent de temps en temps lors de l'exécution d'un algorithme tout en laissant des périodes relativement longues entre deux occurrences, ce qui peut permettre à l'algorithme d'avoir une partie d'exécution sans pannes suffisamment longue pour pouvoir obtenir les résultats attendus. Une variante de l'auto-stabilisation a été introduite en 1999 par Bui & al. : la stabilisation instantanée. Alors qu' un algorithme auto-stabilisant, après l'arrêt des pannes, peut ne pas répondre pendant un temps fini (phase de stabilisation) à la spécification du problème qu'il est censé résoudre et peut notamment nécessiter un nombre fini mais non borné d'essais, un algorithme instantanément stabilisant satisfait immédiatement la spécification après l'arrêt des pannes, en particulier un seul essai est alors nécessaire. Dans cette thèse nous avons proposé deux algorithmes instantanément stabilisants de PIF (Propagation d'Information avec Feedback), le premier pour un arbre non-orienté, le second pour un graphe connexe quelconque. Nos solutions sont les premières de la littérature dans le cadre du modèle à passage de messages (modèle pour les systèmes distribués le plus proche de la réalité) et constituent un pas important pour généraliser à ce modèle le résultat de Cournier & al. de 2003 pour le modèle à états (modèle théorique) selon lequel, dans un système non anonyme, tout problème admettant une solution auto-stabilisante admet aussi une solution instantanément stabilisante.
