L'autostabilisation, ou auto-stabilisation, est la propriété d'un système réparti, composé de plusieurs machines capables de communiquer entre elles, qui consiste, lorsque le système est mal initialisé ou perturbé, à retourner automatiquement à un fonctionnement correct en un nombre fini d'étapes de calcul. Elle a été définie par Edsger Dijkstra en 1974. Essentiellement analysée en informatique théorique, l'autostabilisation vise des applications dans les domaines où l'intervention d'un humain pour rétablir le système après une défaillance est impossible ou dans lesquels il est préférable de s'en passer : les réseaux informatiques, les réseaux de capteurs et les systèmes critiques, tels que les satellites.

Application possible : les réseaux de capteurs

Un réseau de capteurs sans fil est un ensemble de petites machines autonomes, les capteurs. Chaque capteur possède un microprocesseur, une petite quantité de mémoire vive, une batterie, un émetteur-récepteur de radio et un ou plusieurs instruments de mesure : thermomètre, hygromètre, etc. Le but d'un tel réseau est de rassembler automatiquement les mesures effectuées par les capteurs individuels pour en déduire un résultat global. Parmi les applications, les réseaux de capteurs peuvent être déployés dans une forêt pour avertir en cas d'incendie, dans une zone de conflit pour détecter la présence d'ennemis, ou dans un biotope afin d'observer des animaux sans les perturber. Les capteurs étant limités à des processeurs rudimentaires, leur puissance de calcul est limitée. De plus, leurs batteries sont réduites et la consommation en énergie augmente avec la portée des transmissions radio, ce qui limite la distance de leurs communications. En effet, comme les capteurs sont surtout utilisés dans les endroits difficiles d'accès, il n'est généralement pas prévu d'intervenir sur eux pour remplacer la batterie. En général, l'information en provenance des capteurs est récupérée par une station de base (schéma ci-contre) qui possède une plus grande puissance de calcul et de transmission. En règle générale, les capteurs sont fixes : on les pose à un endroit donné et ils ne peuvent pas se déplacer.

Un réseau de capteurs, pour être utile, doit être autonome. Les capteurs doivent s'échanger leurs informations et effectuer leurs traitements sans jamais nécessiter d'intervention. Or, de nombreuses perturbations du système peuvent se produire. Par exemple, un capteur peut tomber en panne, ou de nouveaux capteurs peuvent être déployés dans la zone. L'autostabilisation est une des solutions permettant de s'assurer que le réseau de capteurs récupère automatiquement de ces perturbations.

Des algorithmes autostabilisants peuvent résoudre les problèmes de base spécifiques aux réseaux de capteurs, en particulier le multiplexage temporel (les capteurs s'accordent sur des créneaux pendant lesquels un seul d'entre eux émet), la communication par diffusion orientée (une méthode de routage adaptée aux réseaux de capteurs), et le fonctionnement en dépit du fait que certains capteurs peuvent être périodiquement coupés du reste du réseau. De même, des solutions autostabilisantes adaptées aux réseaux de capteurs existent pour des problèmes classiques tels que la coloration de graphe, le calcul d'un stable maximum ou d'un arbre couvrant, ou encore la synchronisation d'horloges.

Il existe également des réseaux de capteurs mobiles, dans lesquels les capteurs sont posés sur des agents capables de se déplacer. Ceci donne une nouvelle façon d'observer des animaux sauvages sans perturber leur comportement en installant les capteurs non plus dans le biotope, mais sur les animaux eux-mêmes. Les conditions nécessaires et suffisantes pour résoudre le problème du comptage autostabilisant, qui consiste à déterminer le nombre de capteurs présents dans le système, ont été établies dans ce cadre. Cette problématique rejoint celle des protocoles de populations, qui avait été formulée séparément, et qui consiste à considérer le système comme un ensemble d'agents à mémoire très limitée qui se déplacent aléatoirement, capables de s'échanger des informations lorsqu'ils se rencontrent.

Définitions

L'autostabilisation est définie dans le formalisme de l'algorithmique répartie, dont elle est une branche. Les définitions ci-dessous se limitent à ce qui est nécessaire pour caractériser l'autostabilisation.

Modèle Un système5-9 est un ensemble de n processus. Chaque processus possède des variables dans lesquelles sont enregistrées les informations que possède le processus. La collection des variables d'un processus est son état.

Deux modèles existent pour représenter les communications entre processus. Le premier modèle est à passage de messages : les processus peuvent communiquer en s'envoyant des messages via des canaux FIFO. Dans ce cas, l'existence ou non d'un canal entre deux processus donnés est définie par la topologie du réseau. L'état d'un canal est défini comme la séquence des messages qu'il contient. Le deuxième modèle est à mémoire partagée. Dans ce cas, il existe un certain nombre de registres partagés et il faut définir quels processus peuvent lire et écrire dans quels registres. L'état d'un registre est la valeur qu'il contient. La configuration du système est la collection de l'état de tous les processus et moyens de communication.

thumb|upright=1.5|alt=schéma expliquant l'autostabilisation|left|Principe de l'autostabilisation : le système, initialisé dans une configuration quelconque, finit par atteindre une configuration sûre. Toutes les configurations par lesquelles il passe ensuite sont sûres.

Un pas c→c' du système est défini comme l'exécution d'une transition par un ou plusieurs processus tel que le système est au départ dans la configuration c, puis, en exécutant une action, passe dans la configuration c'. Au cours d'une transition, un processus peut recevoir un message (resp. lire un registre partagé dans le cas d'un modèle à mémoire partagée), changer d'état, et envoyer des messages (resp. écrire dans des registres partagés).

Une exécution est une suite alternée infinie de configurations et de pas : E = (c0,a1,c1,a2,c2,…) telle que pour tout i > 0, l'action ai fait passer le système de la configuration ci-1 à la configuration ci. Elle est dite équitable si elle ne contient pas de séquence infinie de pas au cours de laquelle une certaine transition pourrait être exécutée, mais ne l'est jamais. En d'autres termes, dans une exécution équitable, aucun processus n'est privé de la possibilité d'effectuer une certaine transition.

Autostabilisation Pour tout système autostabilisant, on définit un ensemble ℒ d'exécutions légitimes. Cet ensemble représente les exécutions dans lesquelles le système se comporte toujours correctement. Une configuration c est dite sûre vis-à-vis de ℒ si et seulement si toute exécution commençant par c est dans ℒ. Un système est autostabilisant vers ℒ si et seulement si toute exécution de ce système, quelle que soit la configuration de départ, atteint une configuration sûre vis-à-vis de ℒ9.

Propriété fondamentale Un système est autostabilisant si et seulement si on peut associer à toute configuration une valeur prise dans un ensemble muni d'un ordre bien fondé tel que tout pas de l'exécution fait passer le système dans une configuration de valeur , l'inégalité étant stricte si le système commence dans une configuration non sûre. Les valeurs minimales correspondent à des configurations sûresp. 31. Cette propriété, démontrée par Gouda, est utilisable pour démontrer qu'un algorithme est autostabilisant, de la même façon qu'elle peut servir à démontrer qu'un algorithme séquentiel s'arrête.

Mesures de complexité La mesure de l'efficacité d'un algorithme est l'objet de l'analyse de la complexité des algorithmes. Elle définit des méthodes permettant de calculer les performances d'un algorithme, principalement selon deux axes : le temps de calcul et la quantité de mémoire utilisée. Dans le cas de l'autostabilisation, on définit le temps de stabilisation comme le temps le plus élevé que le système peut mettre à atteindre une configuration sûre. Dans un système asynchrone, qui ne dispose pas de notion de temps, on définit une ronde comme la plus courte séquence de pas de l'exécution au cours de laquelle chaque processus est activé au moins une fois, ce qui donne une unité dans laquelle on peut exprimer un temps de stabilisation. Les autres mesures de complexité définies dans les systèmes répartis s'appliquent aussi en autostabilisation : on peut ainsi chercher à échanger le moins possible de messages ou à utiliser un minimum de mémoire sur chaque processus11.

Interprétation en pratique

À la suite de tout incident qui change l'état du système, l'autostabilisation assure de retrouver automatiquement, après un certain temps de fonctionnement sans nouvel incident, une exécution légitime, et donc un fonctionnement correct. En particulier, cela permet de tolérer toute défaillance transitoire, modification arbitraire de l'état d'un processus au cours d'une exécution. Une telle défaillance peut être causée, par exemple, par un rayon cosmique frappant un circuit intégré. Elle peut aussi être due au fonctionnement du système dans de mauvaises conditions, en particulier en cas de surchauffe ou de surcadencement. Une défaillance transitoire laisse le système dans une configuration quelconque, totalement imprévisible. Ce retour automatique à la normale est particulièrement souhaitable dans un système sur lequel il n'est pas possible de faire intervenir un technicien1, par exemple un satellite.

Dans la plupart des systèmes informatiques, le programme lui-même est une donnée enregistrée en mémoire vive. En conséquence, il est sujet aux défaillances transitoires, ce qui empêche l'autostabilisation. La solution est d'enregistrer le programme en mémoire morte. Si le programme doit être chargé en mémoire vive, un chien de garde peut le recharger à partir de la ROM en cas de besoin. Une autre possibilité est de réaliser directement le programme sous forme de circuit intégré.

Anneau à jeton de Dijkstra et historique

Le concept d'autostabilisation est formulé pour la première fois par Dijkstra en 1974Certains auteurs, par exemple Shlomi Dolev dans son livre Self-Stabilization, parlent d'une précédente parution en 1973, mais elle ne figure sur aucun catalogue officiel. D'autre part, Dijkstra, dans son article de 1986 A Belated Proof of Self-Stabilization, indique qu'il a publié son article fondateur en 1974. dans un article qui présente trois algorithmes autostabilisants basés sur le concept d'anneau à jeton. Le principe de l'anneau à jeton est de résoudre le problème de l'exclusion mutuelle en faisant circuler un jeton, qui représente le droit pour le seul processus qui le possède d'effectuer une action qui poserait problème si plusieurs processus l'effectuaient en même temps, par exemple envoyer du texte à une imprimante : un processus qui veut imprimer doit d'abord attendre de recevoir le jeton, puis envoyer son texte à l'imprimante ; après quoi, il perd le jeton. Dans le cas d'un anneau à jeton autostabilisant, si le système est perturbé par l'introduction d'un ou plusieurs jetons supplémentaires, il récupère de lui-même de cette défaillance en supprimant tous les jetons présents sur l'anneau, sauf un ; puis il poursuit son exécution en passant l'unique jeton restant comme s'il n'y en avait jamais eu d'autre.

Les n processus (avec n impair), numérotés de 0 à n-1, sont reliés en anneau, c'est-à-dire que le processus i a comme voisin de droite i+1 modulo n et comme voisin de gauche i-1 modulo n. Autrement dit, le voisin de gauche du processus 0 est le processus n-1 et le voisin de droite du processus n-1 est le processus 0. Chaque processus a un état entier compris entre 0 et 2. On note É l'état d'un processus, D l'état de son voisin de droite et G celui de son voisin de gauche.