Taxonomie des défaillances dans les systèmes répartis 

Taxonomie des défaillances dans les systèmes répartis 

Spécificités des systèmes répartis

Pour réaliser les différentes fonctions demandées à un système réparti, on a développé des algorithmes spécifiques adaptés au contexte réparti : les algorithmes répartis. Les différences entre les systèmes répartis et les systèmes centralisés tiennent en trois points essentiels:
Localité des Informations : Dans un système centralisé, l’état global du système peut être connu à tout instant par le programme en cours d’exécution : cet état global est en général déterminé seulement par l’état des variables et par le compteur de programme. Dans un système réparti, chaque programme en cours d’exécution (ou processus) ne possède qu’une connaissance locale donc partielle de l’état du système. D’autre part, l’état du système de communication ne peut jamais être observé directement par les processus.
Localité du temps : Dans un système centralisé, l’unique processeur exécute les actions de son programme séquentiellement à une vitesse donnée. Il lui est facile de déterminer combien d’actions ont été nécessaires à l’établissement d’une tâche, combien de temps il a fallu pour que le système donne un résultat correct. Dans un système réparti, les événements ne sont plus totalement ordonnés mais organisés selon une relation d’ordre partiel.
Non déterminisme : Du fait de l’hétérogénéité possible des processeurs et des liens de communication dans un système réparti, il est tout à fait possible que ces différents composants agissent à des vitesses différentes, et par conséquent induisent des comportements non déterministes.

Topologie

La notion de voisinage est essentielle dans un système réparti, elle permet d’établir avec quelles autres entités un processus peut communiquer. Pour l’obtenir, on introduit la notion de topologie qui indique la manière d’interconnexion entre les processus et les liens.
Classiquement, on représente la topologie d’un système réparti par un graphe (le graphe de communication) où les processus sont les nœuds du graphe et les liens de communication entre les processus sont les arêtes (ou les arcs si les liens sont unidirectionnels). Le choix d’une topologie dépend du problème traité et de l’avantage que représentent ses caractéristiques.
Topologie en anneau : un anneau à n sommets est un graphe où il existe une numérotation des sommets de s0 à sn−1 telle que les arêtes sont du type (si, si+1) (les indices sont pris modulo n).
Topologie en étoile : un réseau est en étoile s’il possède un nœud central, et n − 1 arêtes connectant les n − 1 autres nœuds au centre.
Topologie en chaîne : une topologie dont les nœuds et les arêtes forment un chemin simple.
Topologie en arbre : un arbre à n nœuds est un graphe connexe à n − 1 arêtes. Cette définition implique qu’un arbre ne contient pas de cycle.
Topologie maillée : une topologie dont le graphe est quelconque.

Systèmes répartis dynamiques

Dans le contexte des systèmes répartis, les transferts de données ne sont pas garantis à 100%. Certains liens de communication peuvent être, temporairement ou définitivement, perdus ou surchargés. On parle alors de systèmes répartis dynamiques. Afin de modéliser ce type de systèmes, différents modèles en théorie des graphes ont été proposés, parmi lesquels on trouve les graphes dynamiques. Intuitivement, un graphe dynamique est un graphe évoluant au cours du temps : des nœuds et des arêtes peuvent être supprimés ou rajoutés . Habituellement, cette évolution est continue (seul un certain nombre de sommets, mais pas tous les sommets sont impliqués en même temps).

Configurations et transitions

Un système réparti peut être modélisé par un système de transition qui fait passer le système d’une configuration à une autre via une fonction de transition.
L’état global d’un système réparti à un instant précis est entièrement décrit par une configuration. Cette dernière peut être caractérisé par un vecteur d’états de chaque processus et de chaque lien du système. L’ensemble des configurations est noté C.
Une transition d’un système réparti est l’exécution d’un ou plusieurs pas atomiques par un sous-ensemble non vide des processus du système .Elle ne dépend que d’une partie de la configuration, et n’influence qu’une partie de cette configuration (l’état local d’un processus est déduit de son état local et/ou de l’état de ses voisins). C’est ce qui induit la notion de distribution ou de parallélisme du système. L’ensemble des transitions est noté T .Un système réparti S est une paire (C, T ) où C est un ensemble de configurations et T un ensemble de transitons.
Afin de dissocier le système de transition d’un processus de celui du système réparti, nous utiliserons les termes de configuration et de transition pour désigner le système réparti et les termes d’état et de pas atomique pour décrire le comportement d’un processus.

Notions de base : fautes, erreurs et défaillances

Une défaillance du système survient lorsque le service délivré diverge de l’accomplissement de la fonction du système, c’est-à-dire de ce à quoi le système est destiné. Une erreur est la partie de la configuration du système qui est susceptible d’entraîner une défaillance, c’est-à-dire qu’une défaillance se produit lorsque l’erreur atteint l’interface du service fourni et le modifie. Une faute ou panne est la cause adjugée ou supposée d’une erreur. On voit donc qu’il existe une chaîne causale entre faute, erreur et défaillance.
Il est à noter que dans les systèmes formés par l’interaction de plusieurs sous-systèmes, les notions de faute, d’erreur et de défaillance sont récursives : la défaillance d’un sous-système devient une faute pour le système le plus global.

Classes d’algorithmes tolérants aux défaillances

En fonction du type de défaillances que l’on considère, du type de tolérance que nous voulons mettre en application et du nombre de défaillances que nous voulons tolérer, les systèmes ont ou non la possibilité de tolérer ces défaillances. Les techniques mises en œuvre pour les tolérer sont alors différentes. Ces solutions peuvent être classifiées suivant la visibilité de l’effet des défaillances à un observateur du système (par exemple un utilisateur).
Une solution masquante cache à l’observateur l’occurrence des fautes (si celles-ci restent dans la limite tolérée par le système), alors qu’une solution non masquante ne présente pas cette propriété: l’effet des défaillances est visible pendant un temps plus ou moins long, puis le système recommence à se comporter correctement.
Une approche masquante apparaît a priori préférable, puisqu’elle s’applique à un plus grand nombre d’applications (et en particulier les applications critiques de sécurité). Cependant, une solution masquante est en général plus coûteuse (en ressources, en temps) qu’une solution non masquante, et ne peut tolérer des défaillances que dans la mesure où celles-ci ont été prévues.
Deux classes principales d’algorithmes tolérants aux défaillances peuvent être distinguées : les algorithmes robustes et les algorithmes auto-stabilisants.

Table des matières

Introduction générale
1 Systèmes répartis 
1.1 Généralités 
1.2 Spécificités des systèmes répartis 
1.3 Eléments de base 
1.3.1 Liens
1.3.1.1 Communication par mémoire partagée
1.3.1.2 Communication par échange de messages
1.3.2 Processus
1.4 Classification des systèmes répartis 
1.4.1 Caractéristiques des processus
1.4.2 Caractéristiques des liens de communication
1.4.3 Caractéristiques liées aux vitesses relatives
1.5 Topologie
1.6 Systèmes répartis dynamiques 
1.7 Problèmes classiques en algorithmique répartie
1.7.1 Problèmes statiques
1.7.2 Problèmes dynamiques
1.8 Configurations et transitions 
1.9 Propriétés des exécutions 
1.9.1 Atomicité
1.9.2 Équité
1.9.3 Démon
1.9.4 Spécification
1.10 Conclusion 
2 Tolérance aux défaillances 
2.1 Notions de base : fautes, erreurs et défaillances 
2.2 Taxonomie des défaillances dans les systèmes répartis 
2.2.1 Localisation des défaillances dans le temps
2.2.2 Nature des défaillances
2.2.2.1 Défaillances d’état
2.2.2.2 Défaillances de code
2.3 Classes d’algorithmes tolérants aux défaillances
2.3.1 Les algorithmes robustes
2.3.2 Les algorithmes auto-stabilisants
2.4 L’auto-stabilisation 
2.4.1 Avantages et limites de l’auto-stabilisation
2.4.2 Auto-stabilisation améliorée
2.4.2.1 k-stabilisation
2.4.2.2 Adaptabilité en temps
2.4.2.3 Confinement de fautes
2.4.2.4 Super-stabilisation
2.4.2.5 Stabilisation instantanée
2.4.3 Définitions
2.4.3.1 Correction
2.4.3.2 Convergence
2.4.3.3 Clôture
2.4.4 Auto-stabilisation affaiblie
2.4.5 Preuve de l’auto-stabilisation
2.5 Mesures de complexité 
2.5.1 Complexité en espace
2.5.2 Complexité en temps
2.6 Conclusion 
3 Auto-stabilisation automatique d’algorithmes 
3.1 Classification des modèles d’auto-stabilisation automatique
3.2 Modèles basés sur le maintien de la topologie 
3.2.1 Modèle de Kutten et Patt-Shamir
3.2.2 Modèle de Dolev
3.3 Modèles utilisant une vérification globale et une correction globale 
3.3.1 Modèle de Katz et Perry
3.4 Modèles utilisant une vérification locale et une correction globale 
3.4.1 Modèle de Arora et Gouda
3.4.2 Modèle de Awerbuch et al.-1
3.5 Modèles utilisant une vérification locale et une correction locale 
3.5.1 Modèle de Browne et al
3.5.2 Modèle de Awerbuch et al.-2
3.5.3 Modèle de Varghese et al
3.6 Conclusion 
4 Maintien de la topologie pour l’auto-stabilisation automatique 
4.1 Maintien de la topologie
4.2 Algorithme auto-stabilisant pour le maintien de la topologie
4.2.1 Modèle et hypothèses
4.2.2 Structure de données
4.2.3 Description de l’algorithme
4.2.4 Preuve de l’auto-stabilisation
4.2.4.1 Preuve de la convergence
4.2.4.2 Preuve de la correction
4.2.5 Complexité en temps
4.3 Transformateur général 
4.4 Conclusion 
Conclusion et Perspectives

Télécharger le rapport complet