Autostabilisation (2).

8 Mai 2010 , Rédigé par CHOMOLANGMA Publié dans #TECHNOLOGIES-Informatique

Un nouvel élan

Leslie Lamport.

Bien que l'algorithme présenté ci-dessus ait été utilisé en production^[22], l'article de Dijkstra passe pratiquement inaperçu jusqu'à ce que Leslie Lamport, invité en 1984 à donner une présentation à la conférence PODC, le mentionne comme particulièrement digne d'intérêt^[26]. L'autostabilisation devient alors un sujet à part entière en algorithmique répartie, ce que Lamport considère comme une de ses contributions les plus importantes à l'informatique^{[note 2]}. Des étudiants soutiennent des thèses de doctorat sur l'autostabilisation et se spécialisent dans la recherche sur ce sujet^{[T 1]}^,^{[T 2]}^,^{[T 3]}^,^{[T 4]}. L'autostabilisation est enseignée à l'université dans le cadre de cours sur l'algorithmique répartie^[27]^,^[28].

En 2000 sort Self-Stabilization, un livre écrit par Shlomi Dolev, le premier entièrement consacré à l'autostabilisation. Par la suite, plusieurs manuels d'algorithmique répartie^[29]^,^[30] et de programmation^[31] consacrent un chapitre à ce sujet. Dijkstra reçoit le prix PoDC de l'article influent pour son article de 1974^[32] en 2002, peu avant sa mort. Dès l'année suivante, ce prix est renommé prix Dijkstra en sa mémoire.

Une rencontre internationale sur le thème de l'autostabilisation^[33] est lancée en 1989 sous le nom de WSS, Workshop on Self-Stabilizing Systems (« Atelier sur les systèmes autostabilisants »). En 2003, après cinq éditions de l'atelier, la rencontre devient une conférence internationale renommée SSS, Symposium on Self-Stabilizing Systems^[34]. En 2005, la conférence élargit son sujet et devient Symposium on Stabilization, Safety, and Security of Distributed Systems (« Congrès sur la stabilisation, la sûreté et la sécurité des systèmes répartis »)^[35]. Depuis l'édition de 2003, les actes sont publiés sous forme de livres.

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^{[D 6]}. 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^[36].

La composition équitable

Composition équitable des algorithmes P et Q.

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^{[D 7]} 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^[37] et développée par les mêmes auteurs en 1993^[38], 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^{[D 8]}, 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^[22] avec un algorithme de construction de topologie d'où on peut extraire un anneau^[38].

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^{[note 3]}. 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^[21], les différents composants matériels de base et les logiciels qui les exploitent afin qu'ils permettent l'autostabilisation : le microprocesseur^[21], le système d'exploitation^[39]^,^[40], les pilotes de périphériques^[41] et le système de fichiers^[42]. 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^[43] 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^[44].

Variantes de l'autostabilisation

Selon les circonstances et les problèmes posés, l'autostabilisation est parfois considérée comme inutilement contraignante ou, au contraire, insuffisamment forte. C'est là qu'interviennent des variantes, relâchements ou renforcements de la définition de base.

La pseudo-stabilisation

La pseudo-stabilisation, ou pseudo-autostabilisation^{[D 9]}, est un relâchement des contraintes de l'autostabilisation. Au lieu d'exiger que toute exécution se termine dans ℒ, on exige que toute exécution réalise une tâche abstraite, c'est-à-dire un prédicat sur le système. Par exemple, pour spécifier l'exclusion mutuelle, on peut exiger que tous les processus du système possèdent un privilège donné infiniment souvent, mais que deux processus ne le possèdent jamais en même temps. Ceci ne permet pas de définir les exécutions légitimes, car elles doivent reposer sur l'état du système ; or, dans la définition d'une tâche abstraite, c'est impossible car on ne sait rien de la façon dont les processus sont réalisés. La pseudo-stabilisation est moins forte et moins contraignante que l'autostabilisation, car tout système autostabilisant est pseudo-stabilisant, mais la réciproque est fausse. Burns, Gouda et Miller, qui ont introduit cette notion en 1993, estiment qu'elle est généralement suffisante en pratique^[45].

Première boucle

Perte d'un message

Deuxième boucle

L'exemple classique de pseudo-stabilisation^{[D 10]} illustré ci-dessus est un système dans lequel deux processus s'échangent des messages. En fonctionnement normal, le système est dans l'état A ; il envoie un message, ce qui fait passer le système dans l'état S ; l'autre processus reçoit le message, ce qui fait passer le système dans l'état B ; le deuxième processus envoie à son tour un message, ce qui fait passer le système dans l'état T ; le premier processus reçoit le message, et le système est de retour dans l'état A. Le problème est que le canal par lequel passent les messages peut perdre un message, auquel cas le système récupère de cette perte en passant dans l'état A'. La définition de A' est totalement dépendante de la méthode utilisée pour récupérer de la perte du message ; elle est donc inconnue au niveau de la tâche abstraite. À partir de A', l'exécution se poursuit de façon similaire : A', S', B', T', A', etc.

Comme la perte d'un message peut se produire, le système n'est pas autostabilisant vers la boucle A, S, B, T. D'un autre côté, cette perte de message peut très bien ne jamais arriver, ce qui fait que le système n'est pas non plus autostabilisant vers la boucle A', S', B', T', ni vers l'ensemble des états possibles. En revanche, ce système, sans être autostabilisant, est bien pseudo-stabilisant pour la tâche abstraite selon laquelle les deux processeurs s'échangent des messages à tour de rôle, puisque la perte d'un message ne remet pas en cause cette définition.

La superstabilisation

L'idée de la superstabilisation^{[D 11]}, introduite par Shlomi Dolev et Ted Herman^[46], est de considérer le changement de topologie, c'est-à-dire l'ajout ou le retrait d'un lien de communication dans le système, comme un événement spécial dont tout processus concerné est averti et qui déclenche une procédure appelée section d'interruption. Grâce à cela, le système est capable de garantir qu'une propriété de sûreté particulière, le prédicat de passage, reste toujours vérifiée pendant la stabilisation lorsqu'un changement de topologie se produit à partir d'une configuration sûre. Ceci renforce les garanties données par le système face à un type de défaillance très fréquent en pratique. Plusieurs problèmes de base de l'algorithmique répartie ont été résolus par un algorithme superstabilisant, par exemple l'exclusion mutuelle^[47], la construction d'un arbre couvrant^[48] et la construction d'un arbre de Steiner^[49].

La stabilisation instantanée

Au lieu de laisser le système appliquer son algorithme et se corriger si nécessaire, il est possible de faire l'inverse : surveiller le système en permanence pour chercher les incohérences et les corriger immédiatement, avant de laisser un pas s'effectuer. Ainsi, le système se comporte toujours conformément à sa spécification : il est autostabilisant en zéro étape^[50]. Un système instantanément stabilisant résiste donc parfaitement aux défaillances transitoires, sans qu'un observateur ne s'aperçoive qu'elles se sont produites.

Pour le moment, seuls quelques algorithmes basiques instantanément stabilisants ont été développés, par exemple pour le problème du parcours en profondeur d'un arbre^[51] ou la communication point à point dans un réseau commuté^[52]. Il est possible de rendre instantanément stabilisant tout algorithme autostabilisant en mémoire partagée, mais la transformation a un coût élevé^[53]. Enfin, la stabilisation instantanée est utilisable dans les systèmes à passage de messages, mais là encore, avec un surcoût considérable^[54].

L'approche probabiliste

Dans une version étendue de son article fondateur^[55], Dijkstra établit qu'il ne peut pas exister d'algorithme d'anneau à jeton autostabilisant dans lequel tous les processus sont identiques, à moins que la taille de l'anneau ne soit un nombre premier. En 1990, Ted Herman apporte un moyen de surmonter cette limitation : obliger l'ordonnanceur à se comporter non plus de façon non-déterministe, mais de façon probabiliste^{[D 4]}, avec pour preuve de concept l'algorithme d'anneau à jeton autostabilisant probabiliste suivant^[56] : le nombre de processus est impair, et l'état de chaque processus est un bit, qui ne peut donc valoir que 0 ou 1. Un processus possède un jeton si et seulement si son état est le même que celui de son voisin de gauche. Dans la configuration (1) ci-dessous, le processus 0 a un jeton car son état est 1, comme pour le processus 4, et aucun autre processus n'a de jeton. Tout processus qui a un jeton est susceptible d'être choisi par l'ordonnanceur pour changer d'état. Dans ce cas, son nouvel état est tiré au sort : 0 ou 1, avec probabilité ½.

Configuration (1)

Configuration (2)

L'interprétation de cette règle en pratique est que le processus a une chance sur deux de garder son jeton, et une chance sur deux de le passer au processus suivant sur l'anneau. Dans la configuration (1), si le processus qui a le jeton tire l'état 1, rien ne change. S'il tire l'état 0, il n'a plus de jeton, car son nouvel état est identique à celui de son voisin de gauche. En revanche, le processus 1 a maintenant un jeton, car il a le même état que son voisin de gauche.

Dans la configuration (2), trois processus ont un jeton. Selon le processus choisi par l'ordonnanceur et le résultat du tirage au sort, après un pas de l'exécution, il peut rester trois jetons ou seulement un. Ainsi, si le processus 1 est choisi, il peut soit garder son jeton, soit le transmettre au processus 2, ce qui ne change pas le nombre de jetons. Mais si le processus 0 est choisi et tire l'état 0, non seulement il perd son jeton, mais le processus 1 perd également le sien. Un ordonnanceur non-déterministe, comme celui utilisé par Dijkstra, pourrait obliger les processus à passer leurs jetons sans jamais les perdre, mais un ordonnanceur probabiliste ne peut pas le faire, car la perte du jeton a une probabilité strictement positive : au cours d'une exécution infinie, elle se produit donc avec probabilité 1.

Dans le cas d'un algorithme probabiliste, il n'est pas possible de calculer un temps de stabilisation, car celui-ci dépend des tirages aléatoires. En revanche, il est possible de calculer son espérance. Initialement, Herman démontre^[56] que l'espérance du temps de stabilisation de son algorithme est O(n² log n) étapes. Un calcul plus précis montre par la suite^[57] que cette espérance est exactement Θ(n²) étapes. Des recherches plus récentes donnent un cadre général basé sur la théorie des chaînes de Markov pour effectuer ces calculs de complexité dans le modèle probabiliste^[58].