Doctorat
Equipe : Parallélisme
Auto-stabilisation efficace
Début le 01/09/1995
Direction : BEAUQUIER, Joffroy
Ecole doctorale :
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI
Soutenue le 02/01/2000 devant le jury composé de :
Joffroy Beauquier
Dominique Gouyou-Beauchamps
Christian Lavault
Michel Raynal
Vincent Villain
Activités de recherche :
- Algorithmique répartie
- Autostabilisation
- Algorithmes probabilistes
- Théorie des graphes
- Complexité
Résumé :
Quand un système réparti est sujet à des défaillances transitoires qui modifient arbitrairement son état, il est crucial de pouvoir retrouver un comportement correct au bout d'un temps fini. L'auto-stabilisation présente une telle garantie, mais en général au prix de ressources importantes. Dans cette thèse, notre démarche a consisté à minimiser ces ressources lorsque cela était possible.
Nous avons développé le concept de détecteur de défaillances transitoires, des oracles appelés par les processeurs du système, qui indiquent si des défaillances transitoires sont survenues, en un temps constant. Notre implantation permet de classifier les problèmes classiques suivant les ressources spécifiques nécessaires à la détection d'une erreur. Pour les tâches statiques, une suite naturelle a été de montrer qu'une condition sur le code localement exécuté par chaque processeur pouvait être suffisante pour garantir l'auto-stabilisation du système tout entier, indépendamment des hypothèses d'exécution et de la topologie du graphe de communication. Du fait que l'algorithme n'est pas modifié, il est forcément sans surcoût. De manière duale, nous avons développé des outils de synchronisation permettant de construire des algorithmes auto-stabilisants pour des spécifications dynamiques avec un surcoût en mémoire constant, c'est à dire indépendant de la taille du réseau. En outre, l'un des algorithmes présentés est instantanément stabilisant. Enfin, nous avons présenté une technique générale pour réduire systématiquement le coût des communications, en garantissant un délai de retransmission borné, et nous avons donné un cadre général ainsi que des outils d'implantation pour écrire des algorithmes auto-stabilisants dans ce contexte.
Pour en savoir plus: http://tel.archives-ouvertes.fr/tel-00124843
