Correction de défaillances transitoires dans les sytèmes auto-stabilisants
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
Self-stabilizing systems, introduced by E. W. Dijkstra in 1974, are distributed systems tolerating transient failures. This model of fault includes a large class of possible behaviour: every process state and communication channel memory can be reset to an arbitrary value, a finite number of times. Whatever is the initial configuration of a self-stabilizing system, eventually, it will behave accordingly its specification. The part of the execution, which let the system reach a correct behaviour, is called the convergence phase. Meanwhile this period, the system can break its specification. This PhD thesis presents different techniques to verify good properties on self-stabilizing systems during their convergence phase. First, we have defined a new notion, the transient failure corrector, which is a tool designed to measure the locality of problems with respect to the failure mending problem. We illustrated this notion, giving minimal and maximal bounds for large classes of problems, in which we included classical problems of distributed systems. Then, we proposed generic self-stabilizing algorithms transformers, to ensure that the convergence time is proportional to a bound on the number of tolerated failures, or with different assumptions, to the effective number of transient failures in the initial configuration. Last, we formalize and study a new tool for transient failure mending: the mobile agent. We define the notion of agent-stabilizing systems; we propose agent-stabilizing circulation algorithms, and illustrate the power of agents as a fault mending tool on classical problems of distributed systems.
Abstract FR:
Les systèmes auto-stabilisants, introduits par E. W. Dijkstra en 1974 sont des systèmes distribués tolérants aux défaillances transitoires. Ce modèle de défaillances inclus une large classe de fautes possibles: tous les processus et canaux de communications peuvent voir leur état (leur mémoire) réinitialisée à une valeur quelconque, un nombre fini de fois. Quelque soit l'état dans lequel un système auto-stabilisant est démarré, au bout d'un temps fini, il se comporte selon sa spécification. La partie de l'exécution qui permet au système d'atteindre un comportement correct est appelé phase de convergence. Pendant cette phase, le système peut violer sa spécification. Ce travail de thèse a consisté à étudier différentes techniques pour garantir de bonnes propriétés aux systèmes auto-stabilisants pendant leur phase de convergence. Dans un premier temps, nous avons défini une nouvelle notion, le correcteur de défaillances transitoires, qui permet de mesurer le degré de localité des problèmes relativement au problème de la correction de défaillances transitoires. Nous avons illustré l'utilisation de cette notion en donnant des bornes minimales et maximales pour de grandes classes de problèmes dans lesquelles nous avons inclus des problèmes classiques de l'algorithmique distribuée. Ensuite, nous avons proposé des transformateurs génériques d'algorithmes auto- stabilisants, pour garantir que le temps de convergence est proportionnel à une borne sur le nombre de défaillances, ou avec d'autres hypothèses au nombre effectif de défaillances dans la configuration initiale du système. Enfin, nous avons formalisé et étudié un nouvel outil pour la correction de défaillances transitoires: l'agent mobile. Nous avons défini la notion de système stabilisant par agent mobile; proposé de nombreux algorithmes de circulation d'agents et illustré les techniques de correction sur des problèmes classiques de l'algorithmique distribuée.