Autostabilisation

Un système[D 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.

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 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 = (c₀,a₁,c₁,a₂,c₂,…) tel que pour tout i > 0, l'action a_i fait passer le système de la configuration c_i-1 à la configuration c_i. 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.

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 ℒ[D 2].

Un système est autostabilisant si et seulement si on peut associer à toute configuration une valeur prise dans un anneau noethérien tel que tout pas de l'exécution commençant dans une configuration non sûre de valeur v fait passer le système dans une configuration de valeur v'<v, et les valeurs les plus basses de l'anneau correspondent aux configurations sûres[D 3]. Cette propriété, démontrée par Gouda[18], 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.

La mesure de l'efficacité d'un algorithme est l'objet de la 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[19]. 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[D 2]. 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 processus[D 4].

À 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é[20]. 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 technicien[D 5], 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[21] 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é.

Configuration initiale (1) : seul le processus 0, en rouge, a un privilège.

À chaque pas de l'exécution, un processus est choisi arbitrairement par un ordonnanceur. En pratique, cet ordonnanceur dépend du matériel, du système d'exploitation et de l'environnement dans lequel il fonctionne ; son comportement est donc imprévisible. Le côté arbitraire de ce choix est à la base de la motivation initiale de Dijkstra, qui cherche à savoir si un système peut se comporter correctement en dépit d'un contrôle réparti. Dans cet algorithme, seuls les processus qui ont un privilège peuvent réagir lorsqu'ils sont choisis, en changeant d'état. Les privilèges et les changements d'état associés sont définis par les règles suivantes :

1. Pour le processus 0 : si (É+1) mod 3 = D alors É ← (É-1) mod 3
2. Pour le processus n-1 : si G=D et (G+1) mod 3 ≠ É alors É ← (G+1) mod 3
3. Pour tous les autres processus :
   • si (É+1) mod 3 = G alors É ← G
   • si (É+1) mod 3 = D alors É ← D

Ici, le privilège représente le fait pour un processus de posséder un jeton. Pour comprendre comment fonctionne cet algorithme lorsqu'il existe un unique privilège, considérons le cas ci-contre. Les numéros de processus sont en noir, les états en bleu. Le processus 0 a un privilège, matérialisé en rouge, en application de la règle 1. En effet, son état est 1 ; en ajoutant 1, on obtient 2, ce qui est l'état de son voisin de droite. En revanche, aucun autre processus n'a de privilège : le processus 4 parce que les états de ses voisins ne sont pas égaux, les autres processus parce qu'aucun processus n'a l'état (2+1) mod 3 = 0.

Lors du premier pas de l'exécution, c'est donc le processus 0 qui change d'état. En application de la règle 1, il prend l'état 1-1 = 0. Ceci donne un privilège au processus 1, qui change donc d'état lors du pas suivant de l'exécution. Celle-ci continue ainsi :

• 
  Configuration (2)
• 
  Configuration (3)
• 
  Configuration (4)
• 
  Configuration (5)

Dans la configuration (5), le processus 4 a le privilège. Il change donc d'état en application de la règle 2, prenant l'état 0+1=1. Ceci donne le privilège au processus 3.

• 
  Configuration (6)
• 
  Configuration (7)
• 
  Configuration (8)
• 
  Configuration (9)

Le privilège a été passé, de proche en proche, à tous les processus. La configuration (9) est équivalente à la configuration (1) ; le système est donc prêt à recommencer à passer le privilège selon le même principe. Le constat que « tout se passe bien » montre, informellement, que cette exécution est légitime.

Pour comprendre comment l'algorithme garantit que le nombre de privilèges atteint forcément 1, il faut d'abord remarquer que les règles ne permettent aucune situation où il n'existerait pas de privilège. En effet, en vertu de la règle 3, dans une telle configuration, les processus dont les numéros vont de 1 à n-2 doivent tous avoir le même état e ; de plus, les processus 0 et n-1 doivent avoir soit l'état e, soit l'état (e-1) mod 3. Or, si le processus 0 a l'état (e-1) mod 3, alors il a un privilège ; si le processus n-1 a l'état (e-1) mod 3, alors il a un privilège.

La preuve de correction de cet algorithme, publiée en 1986[24], s'appuie sur le fait que si plusieurs privilèges existent, alors leur nombre doit nécessairement diminuer. Pour cela, Dijkstra démontre qu'entre deux changements d'état du processus n-1, il se produit forcément un changement d'état du processus 0. Il prouve ensuite qu'il n'existe pas de séquence de pas infinie dans laquelle le processus 0 ne change pas d'état. Enfin, il établit la liste des scénarios possibles pour le comportement du privilège situé le plus à gauche sur l'anneau et démontre que ce privilège disparaît. Par récurrence, après un certain nombre de pas, il ne reste finalement qu'un seul privilège.

• 
  Premier cas de collision
• 
  Deuxième cas de collision

Pour voir comment les privilèges surnuméraires disparaissent, il suffit de constater, dans l'exécution normale ci-dessus, que les privilèges circulent de la gauche vers la droite à partir du processus 0 et de la droite vers la gauche à partir du processus n-1. En conséquence, s'il y a deux privilèges sur l'anneau, ils finissent par se rencontrer. Cette situation est illustrée ci-dessus par le premier cas de collision, où ni le processus 0, ni le processus n-1 n'est impliqué. Dans ce cas, dès que l'un des processus privilégiés change d'état, il perd son privilège alors que l'autre processus garde le sien : le nombre de privilèges a diminué de 1.

Le cas de la collision des processus 0 et 1 est particulier (deuxième cas de collision ci-dessus). En effet, si 1 change d'état, son privilège change simplement de « sens », allant désormais de la gauche vers la droite. Cependant, il peut franchir le processus n-1 et doit donc disparaître. Si c'est le processus 0 qui change d'état, de façon analogue, son privilège passe au processus n-1.

Dijkstra n'aborde pas la question du temps de stabilisation de son algorithme, ni dans son article original de 1974[22], ni dans l'article de 1986 dans lequel il donne la preuve de correction[24]. En 2007, une équipe sans lien avec Dijkstra démontre que cet algorithme se stabilise en O(n²) étapes[25].

Leslie Lamport.

Bien que l'algorithme présenté ci-dessus ait été utilisé en production[22], l'article de Dijkstra passe presque 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.

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].

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].

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].

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.

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].

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 réseau identifié quelconque[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].

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].

• Références issues de Self-Stabilization

• Références à des thèses de doctorat

• Autres références

: document utilisé comme source pour la rédaction de cet article.

• (en) Shlomi Dolev, Self-Stabilization, The MIT Press, 3 mars 2000, 207 p. (ISBN 978-0-262-04178-2, présentation en ligne)
  
• (en) Vijay Kumar Garg, Elements of Distributed Computing, Wiley-IEEE Press, 23 mai 2002, 423 p. (ISBN 978-0-471-03600-5, présentation en ligne)
• (en) Vijay Kumar Garg, Concurrent and Distributed Computing in Java, Wiley-IEEE Press, 4 février 2004, 336 p. (ISBN 978-0-471-03600-5, présentation en ligne)
• (en) Gerard Tel, Introduction to Distributed Algorithms, Cambridge University Press, 15 février 2001, 608 p. (ISBN 978-0-521-79483-1, présentation en ligne)

Depuis l'édition de 2003, les actes de la conférence SSS sont publiés sous forme de livres dans la collection Lecture Notes in Computer Science de Springer Verlag. L'autostabilisation est le seul thème de la conférence jusqu'en 2005, l'un des principaux thèmes par la suite.

• (en) Shing-Tsaan Huang (dir.) et Ted Herman (dir.), Self-Stabilizing Systems : 6th International Symposium, SSS 2003, San Francisco, Ca, USA, June 24-25, 2003 Proceedings, Springer Verlag, 11 juin 2003, 215 p. (ISBN 978-3-540-40453-8, présentation en ligne)
• (en) Sébastien Tixeuil (dir.) et Ted Herman (dir.), Self-Stabilizing Systems : 7th International Symposium, SSS 2005, Barcelona, Spain, October 26-27, 2005 (Lecture Notes in Computer Science), Springer Verlag, 27 octobre 2005, 229 p. (ISBN 978-3-540-29814-4)
• (en) Ajoy Kumar Datta (dir.) et Maria Gradinariu Potop-Butucaru (dir.), Stabilization, Safety, and Security of Distributed Systems : 8th International Symposium, SSS 2006 Dallas, TX, USA, November 17-19, 2006 Proceedings (Lecture Notes in Computer Science), Springer Verlag, 8 novembre 2006, 805 p. (ISBN 978-3-540-49018-0)
• (en) Toshimitsu Masuzawa (dir.) et Sébastien Tixeuil (dir.), Stabilization, Safety, and Security of Distributed Systems : 9th International Symposium, SSS 2007 Paris, France, November 14-16, 2007 Proceedings (Lecture Notes in Computer Science), Springer Verlag, 6 novembre 2007, 409 p. (ISBN 978-3-540-76626-1)
• (en) Sandeep Kulkarni (dir.) et André Schiper (dir.), Stabilization, Safety, and Security of Distributed Systems : 10th International Symposium, SSS 2008, Detroit, MI, USA, November 21-23, 2008, Springer Verlag, 6 novembre 2008, 265 p. (ISBN 978-3-540-89334-9)
• (en) Rachid Guerraoui (dir.) et Franck Petit (dir.), Stabilization, Safety, and Security of Distributed Systems : 11th International Symposium, SSS 2009, Lyon, France, November 3-6, 2009. Proceedings, Springer Verlag, 26 octobre 2009, 805 p. (ISBN 978-3-642-05117-3)

• Algorithmique répartie
• Tolérance aux pannes
• Système critique
• Réseau de capteurs sans fil

• (en) Page d'accueil de SSS, la conférence sur l'autostabilisation
• (en) Site web de Shlomi Dolev, avec des informations sur son livre et ses publications
• (fr) [PDF] Notes prises par Philippe Gambette sur un cours de Joffroy Beauquier et Laurent Fribourg concernant l'algorithmique répartie, dont l'autostabilisation, anciennement mises à disposition sur le site du master parisien de recherche en informatique