Mots-clés: autostabilisation
Définition
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.
Une application possible : les réseaux de capteurs
Un réseau de capteurs sans fil1 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'incendie2, dans une zone de conflit pour détecter la présence d'ennemis3,4, ou dans un biotope afin d'observer des animaux sans les perturber5. 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 perturbations6.
Des algorithmes autostabilisants peuvent résoudre les problèmes de base spécifiques aux réseaux de capteurs, en particulier le multiplexage temporel7 (les capteurs s'accordent sur des créneaux pendant lesquels un seul d'entre eux émet), la communication par diffusion orientée8 (une méthode de routage adaptée aux réseaux de capteurs9), et le fonctionnement en dépit du fait que certains capteurs peuvent être périodiquement coupés du reste du réseau10. De même, des solutions autostabilisantes adaptées aux réseaux de capteurs existent pour des problèmes classiques tels que la coloration de graphe11, le calcul d'un stable maximum11 ou d'un arbre couvrant11, ou encore la synchronisation d'horloges12.
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 comportement13,14 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 cadre15,16. 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 rencontrent17.
Modèle
Un systèmeD 1 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.
Un pas c→c' du système est défini comme l'exécution d'une transition par un processus telle 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. Lire la suite
