Autostabilisation et protocoles réseau

摘要

In 1974, E.W. Dijkstra defined self-stabilization as the property for a distributed system to recover by itself a correct behavior in a finite number of steps, starting from any initial state. Thus, self-stabilization is a simple and efficient way to tolerate transient faults or failures. This paper surveys works that propose self-stabilizing solutions to problems arising in Computer Networks, such as routing and transport layers, or network control protocols. We also review techniques to design self-stabilizing protocols, and mechanisms that reduce the stabilization time when the number of hitting faults is small.%En 1974, Dijkstra a défini l'autostabilisation comme la propriété pour un système réparti de retrouver de lui-même un comportement correct en un nombre fini d'étapes, et ce, quel que soit son état initial. L'autostabilisation constitue donc un moyen simple et efficace de tolérer des fautes ou des pannes transitoires. Cet article est consacré aux travaux proposant des solutions autostabilisantes à des problèmes classiques dans le domaine des réseaux informatiques, notamment dans les domaines du routage, des communications point à point (transport de données) et des protocoles de contrôle. Des techniques de conception de protocoles autosta-bilisants sont également présentées, ainsi que des mécanismes permettant de réduire le temps de stabilisation lorsque le nombre de défaillances est faible.