Abstract FR:

Cette thèse porte sur l'étude des algorithmes répartis tolérant aux pannes. Plusieurs approches ont été proposées dans cette optique, parmi lesquelles l'auto-stabilisation (le système rétablit de lui-même un fonctionnement correct au bout d'un temps fini) et le confinement de fautes (on limite la propagation d'une faute singulière). Nos travaux visent à étendre les champs d'application de ces deux approches. Concernant l'approche auto-stabilisante, nous proposons un algorithme d'ordonnancement des déplacements dans un système de robots mobiles communiquant sur des points de rendez-vous fixés. Cet algorithme garantit que, après la phase de stabilisation, chaque visite à un point de rendez-vous aboutit à une communication. Nous présentons ensuite un algorithme auto-stabilisant pour engendrer et maintenir les tables de routage des robots. Concernant le confinement de fautes, nous présentons un algorithme qui résout le problème de l'élection et de l'arbre couvrant dans un graphe quelconque.