CTL
12 décembre 2013 - 13h30
Algorithmes auto-stabilisants pour la construction de structures couvrantes réparties (Phd Defense)
par Yvan Rivierre de VERIMAG
Résumé : Cette thèse s’intéresse à la construction auto-stabilisante de structures couvrantes dans un système réparti. L’auto-stabilisation est un paradigme pour la tolérance aux fautes dans les algorithmes répartis. Plus précisément, elle garantit que le système retrouve un comportement correct en temps fini après avoir été perturbé par des fautes transitoires.
Notre modèle de système réparti se base sur des mémoires localement partagées pour la communication, des identifiants uniques pour briser les symétries et un ordonnanceur inéquitable, c’est-à-dire le plus faible des ordonnanceurs. Dans la mesure du possible, nous nous imposons d’utiliser les plus faibles hypothèses, afin d’obtenir les constructions les plus générales de structures couvrantes réparties.
Nous présentons quatre algorithmes auto-stabilisants originaux pour le k-partitionnement, la construction d’une (f,g)-alliance et l’indexation. Pour chacun de ces problèmes, nous prouvons la correction de nos solutions. De plus, nous analysons leur complexité en temps et en espace à l’aide de preuves formelles et de simulations. Enfin, pour le problème de (f,g)-alliance, nous prenons en compte la notion de convergence sûre qui vient s’ajouter à celle d’auto-stabilisation. Elle garantit d’abord que le comportement du système assure rapidement un minimum de conditions, puis qu’il continue de converger jusqu’à se conformer à une spécification plus exigeante.
Jury :
- Franck Petit (Pr à l'UPMC), rapporteur
- Ajoy K. Datta (Pr à l'UNLV), rapporteur
- Alain Cournier (Pr à l'UPJV), examinateur
- Fabien Mathieu (HDR, Alcatel-Lucent Bell Labs France), examinateur
- Florence Maraninchi (Pr à Grenoble-INP), directrice
- Fabienne Carrier (Mcf à l'UJF), co-encadrante
- Stéphane Devismes (Mcf à l'UJF), co-encadrant
