Autostabilisation - Définition
La liste des auteurs de cet article est disponible ici.
Construction de systèmes autostabilisants
Des travaux de recherche sur l'autostabilisation permettent de mieux comprendre comment il est possible de construire un algorithme autostabilisant. Il est possible de l'obtenir automatiquement à partir d'un algorithme réparti classique au moyen d'un stabilisateur, ou en composant plusieurs algorithmes eux-mêmes autostabilisants. D'autre part, l'analyse de la question du fonctionnement à bas niveau montre les conditions que le matériel doit remplir pour permettre à l'autostabilisation de fonctionner.
Utilisation d'un stabilisateur
Un stabilisateur est un algorithme qui rend autostabilisant n'importe quel algorithme réparti. La meilleure solution connue pour réaliser un stabilisateur consiste à donner à un processus distingué le rôle d'examiner tout le système, ce qui suppose d'obtenir et enregistrer l'état de tous les autres processus, puis, si nécessaire, remettre le système à zéro de façon autostabilisante. Cette méthode est trop coûteuse en mémoire et en nombre de messages échangés pour être viable en pratique.
La composition équitable
La réutilisation d'algorithmes est une question classique en génie logiciel. Dans le cadre de l'autostabilisation, elle se pose en ces termes : en supposant donnés des algorithmes autostabilisants, est-il possible de les combiner pour obtenir un algorithme global, ou faut-il à chaque fois tout réécrire depuis le début ? La composition équitable apporte la réponse : sous certaines conditions, la réutilisation d'algorithmes autostabilisants est possible.
Introduite par Shlomi Dolev, Amos Israeli et Shlomo Moran en 1989 et développée par les mêmes auteurs en 1993, elle repose sur deux observations. Premièrement, un algorithme Q qui n'écrit pas dans les variables que lit un algorithme P ne peut pas le gêner pour se stabiliser. Deuxièmement, puisque P est autostabilisant, Q peut lire les variables de P pendant sa propre stabilisation : en effet, il est garanti par définition que les valeurs de ces variables finissent par devenir correctes ; à partir de ce moment, Q se stabilise normalement.
Il est donc possible de fusionner les algorithmes P et Q, en ajoutant simplement leurs codes et variables, pour former un nouvel algorithme, noté P⊕Q (voir le schéma ci-contre). Ce nouvel algorithme est lui-même autostabilisant, à condition qu'aucun des algorithmes ne puisse bloquer l'autre ; il faut donc exiger que, dans toute exécution du système global, chacun des deux algorithmes effectue un nombre infini de pas. Cette dernière condition garantit l'équité de l'ordonnancement entre les deux algorithmes, d'où le terme de composition équitable.
Il est ainsi possible de concevoir un algorithme autostabilisant de façon modulaire, en le découpant en sous-algorithmes spécialisés à composer pour obtenir l'algorithme final. Si un algorithme a déjà été écrit pour une tâche donnée, on peut le réutiliser. Par exemple, si on veut faire circuler un jeton sur un système dont la topologie n'est pas en anneau, il suffit de composer l'algorithme de Dijkstra avec un algorithme de construction de topologie d'où on peut extraire un anneau.
Conception d'un matériel autostabilisant
Pour qu'un système puisse réellement être autostabilisant, le matériel sur lequel il fonctionne doit être prévu pour cela. En effet, le matériel ou son micrologiciel peut contenir des bugs qui provoquent son plantage. Il est donc nécessaire de s'assurer que le microprocesseur ne puisse pas se bloquer en entrant dans un état duquel il ne peut plus sortir. La recherche dans ce domaine a permis d'identifier précisément les conditions à remplir par le microprocesseur, les différents composants matériels de base et les logiciels qui les exploitent afin qu'ils permettent l'autostabilisation : le microprocesseur, le système d'exploitation, les pilotes de périphériques et le système de fichiers. D'une façon générale, il s'agit de s'assurer qu'aucun blocage n'est possible, ni dans un état dont le système ne peut sortir, ni dans un ensemble d'états où il tournerait sans fin en boucle. Un compilateur préservant la stabilisation a été conçu pour permettre d'écrire des programmes tirant parti de ces matériels et logiciels : si on lui fournit un programme autostabilisant, il produit un code machine respectant ce même concept d'évitement des blocages. Un brevet a été déposé sur la base de ces résultats.
