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
