Sujet : Tolérances aux pannes et calculs locaux distribués.

Responsable : Mohamed Mosbah
Téléphone : 05 56 84 69 17
e-mail : mosbah@labri.fr
Site Web : http://www.labri.fr/
Equipe : L3A

Présentation du sujet :

On considère un réseau de processeurs ayant une topologie quelconque. Il est
représenté par un graphe étiqueté, connexe, et non orienté, où les sommets
correspondent aux processeurs et les arêtes aux canaux de communication.
L'étiquette d'un sommet (resp. d'une arête) code l'état du processeur
(resp. du lien de communication) correspondant. Un calcul sur un réseau, qui
consiste donc à faire évoluer ces états, peut être décrit par des règles de
réécriture de graphes. Chaque règle, définie par un graphe connexe et deux
étiquetages de ce graphe, traduit une étape élémentaire du calcul effectuée
sur une portion locale du graphe. De nombreux algorithmes distribués
peuvent être exprimés dans ce modèle, on peut citer à titre d'exemple le calcul
distribué d'un arbre recouvrant ou l'élection. Plusieurs paradigmes peuvent
également être exprimés comme la détection locale de la terminaison globale, ou la séquentialité
de l'exécution.
L'objet de cette thèse est d'étudier le modèle sur un réseau avec possibilité de
pannes. Une étiquette spéciale indiquera le (ou les sommets) qui sont en pannes.
Les règles de réécriture doivent tenir compte de ces sommets et fournir une solution correcte.
On pourra introduire des règles de correction permettant de refaire une partie du calcul.
Dans le cas de pannes transitoires, il s'agit d'étudier des algorithmes auto-stabilisants.
Le travail demandé aura également un aspect appliqué qui consiste à implémenter
et à expérimenter les algorithmes étudiés à l'aide de la plate-forme visidia.
Cette thése s'inscrit dans le cadre du projet visidia.


Mot-clés : Tolérance aux pannes, algorithmes distribués, auto-stabilisation.