Un nouveau protocole hiérarchique adaptatif par points de reprise et journalisation

Télécharger le fichier original (Mémoire de fin d’études)

Notion de tolérance aux fautes

De manière générale, une grille informatique est un ensemble de nœuds de calcul reliés par un réseau de communication et communiquant entre eux par messages. Dans ce contexte, la tolérance aux fautes devient une obligation pour assurer le bon fonctionnement du système réparti. Pour comprendre la notion de tolérance aux fautes, nous allons présenter les aspects de la sûreté de fonctionnement d’un système pour comprendre les origines des défaillances dans les systèmes répartis.
La sûreté de fonctionnement (dependability) d’un système peut se définir selon Jean-Claude Laprie dans son guide de la sûreté de fonctionnement, « la propriété qui permet aux utilisateurs du système de placer une confiance justifiée dans le service qu’il leur délivre » [6]. Un système sûr de fonctionnement doit assurer la continuité du service quel que soit les défaillances survenues au cours de son exécution. Cela implique la réparation des fautes ou pannes, qui sont les conséquences de la non-fiabilité du système. Cette fiabilité doit garantir la sécurité. Et toutes ces conditions vont assurer la disponibilité des ressources du système réparti, propriété de base des environnements distribués. Les fautes étant les causes des défaillances, la sûreté de fonctionnement cherche à les combattre, si possible en évitant qu’elles se produisent (prévention), ou en les éliminant (élimination).
Les fautes, les erreurs et les défaillances représentent les entraves à la sûreté de fonctionnement. Une erreur est un état susceptible d’entraîner une défaillance ; la faute est la cause supposée d’une erreur ; la défaillance est la manifestation d’une erreur. La Figure 3 montre la relation de causalité qui existe entre les fautes, les erreurs et les défaillances. Par propagation, plusieurs erreurs peuvent être générées avant qu’une défaillance ne se produise. Lorsque le système est défaillant, il n’est plus apte à assurer le service défini par l’utilisateur [6].
En empêchant ainsi une erreur de se propager, on améliore la sûreté de fonctionnement d’un système tout en tolérant les fautes [6].
Conséquences » Activation » Propagation » Conséquences »
… »Défaillances » Fautes » Erreurs » Défaillances » Fautes »… »
Figure 3 : Entraves à la sûreté de fonctionnement
Le seul moyen d’éviter que cette chaine ne se produise est d’empêcher son activation déclenchée par les fautes survenues dans le système. On distingue deux catégories de fautes selon leur origine:
• Fautes accidentelles : elles sont en général d’origine matérielle, comme par exemple un court-circuit ou une défectuosité d’équipements.
• Fautes intentionnelles : elles sont liées à la sécurité ou bien une mauvaise action sur les logiciels. Elles peuvent aussi concerner les déconnexions de machines.
Dans les environnements répartis, il existe plusieurs types de fautes classés selon le degré de défaillances:
• Fautes franches ou par arrêt total : c’est le modèle de panne le plus simple ; le système arrête subitement de fonctionner et se retrouve dans un état « incorrect ».
• Fautes par omission : ce type de faute survient lorsque des messages sont perdus.
• Fautes par valeur : elles concernent essentiellement les résultats produits par les composants qui peuvent avoir des valeurs incorrectes.
• Fautes byzantines : elles sont très complexes parce que le système continue en présence de messages qui ne suivent pas sa spécification.
• Fautes par temporisation : le comportement erroné du système est dû au temps.
Pour évaluer la sûreté de fonctionnement d’un système, J.-C. Laprie a défini des attributs (Figure 4). Ces six propriétés de base doivent être vérifiées pour garantir la sûreté :
• Fiabilité : elle évalue la continuité du service délivré par le système et défini par l’utilisateur.
• Disponibilité : pour qu’un système soit sûr de fonctionnement, il faut que les ressources soient disponibles à tout moment.
• Maintenabilité : c’est la capacité du système à subir des réparations et des modifications.
• Sécurité : elle doit permettre la résistance aux pannes catastrophiques sur l’utilisateur et l’environnement.
• Confidentialité : la notion de partage dans les systèmes impose la confidentialité sur toutes les informations en mettant en place des mécanismes d’authentification
• Intégrité : c’est un attribut qui permet d’évaluer l’aptitude du système à éviter les altérations de son état.
En fonction de la demande des applications, certains attributs peuvent être mis en valeur plus que d’autres. Par exemple, la disponibilité est toujours nécessaire alors que la fiabilité, la confidentialité ou la sécurité peuvent ne pas être primordiales. Donc les attributs de la sûreté de fonctionnement doivent être interprétés au sens relatif et probabiliste plutôt que dans un sens absolu dans la mesure où les systèmes ne sont jamais totalement disponibles, fiables ou sécurisés.
Il existe d’autres attributs secondaires, liés à la sécurité des informations comme l’authenticité et la non-répudiation. Ces deux propriétés permettent respectivement de garantir l’intégrité du contenu des messages et de connaître l’identité de l’émetteur et du récepteur du message.
Pour que le système vérifie les attributs nécessaires à la sûreté de fonctionnement, des moyens ont été définis dans [6] comme le montre l’arbre de la sûreté de fonctionnement:
• L’élimination des fautes
• La prévision des fautes
• L’évitement des fautes
• La tolérance aux fautes ou tolérance aux pannes
Dans le cas de notre étude, nous nous intéressons à la tolérance aux fautes. L’objectif de la tolérance aux fautes est la préservation de la continuité du service malgré l’apparition de fautes. Du fait de leur nature hétérogène, l’occurrence de fautes dans les grilles est inévitable. Cette nature fait référence à la dynamicité des ressources, de l’hétérogénéité des équipements, des systèmes d’exploitation et applications, de l’absence de mémoire et d’horloge commune, et l’asynchronisme des communications entre les processus. Il est donc primordial de mettre en place des mécanismes permettant au système de continuer à fonctionner, même en présence de fautes. Deux méthodes permettent de tolérer les fautes : la détection d’erreur et la récupération du système. La détection d’erreur est possible grâce aux messages d’erreur émis dans le système. La récupération ramènera ce dernier dans un état antérieur correct, sans erreur. Nous détaillerons cette dernière méthode dans la suite de ce document.

Techniques de tolérance aux fautes dans les grilles

On distingue deux principales techniques de tolérance aux fautes dans les grilles informatiques :
• La réplication
• Le recouvrement arrière
Nous allons présenter ces deux mécanismes en insistant sur la technique de réplication. Les mécanismes de recouvrement arrière seront étudiés de manière plus précise dans le chapitre suivant.

La réplication

La tolérance aux fautes basée sur la réplication consiste à créer des copies multiples des processus sur des machines différentes. Lors de la panne d’un processus, il est remplacé par une de ses copies. La réplication dans un système réparti présente plusieurs avantages. Elle apporte une meilleure sûreté de fonctionnement en augmentant la disponibilité et la fiabilité des données. En effet, elle permet d’éviter la perte de cycle d’exécution en cas de panne en masquant les fautes. La réplication améliore aussi les performances car la répartition des données permet d’éviter les accès multiples à un seul site pouvant réduire les latences du réseau.
Ils existent trois techniques de réplication proposées dans la littérature : la réplication active, passive et semi-active. Les deux premières stratégies de réplication sont les bases et elles constituent les références des autres mécanismes de réplication.

La réplication active

C’est une technique dans laquelle toutes les répliques traitent les mêmes messages d’entrée, mais en gardant leur état étroitement synchronisé pour assurer qu’elles reçoivent les messages dans le même ordre. Chaque réplique joue un rôle identique à celui des autres. Les mêmes messages de sortie sont donc générés et une technique de vote permet de choisir le message à renvoyer.
En cas de panne, les erreurs sont masquées par les copies non défaillantes qui assurent le relais. La défaillance d’une copie est masquée par les autres répliques, donc la défaillance de l’une d’entre elles ne perturbe pas le fonctionnement du système. Il est à noter que grâce au vote sur les messages en sortie des comportements byzantins peuvent être tolérer.

La réplication passive

On distingue deux types de copies de processus dans cette technique : une copie primaire et des copies secondaires. Seule la copie primaire traite les messages d’entrée et fournit les messages de sortie. Pour maintenir la cohérence, la copie primaire transmet par intervalle de temps son nouvel état aux copies secondaires.
En l’absence de fautes, les copies secondaires ne traitent pas les messages d’entrée, mais leur état est régulièrement mis à jour au moyen des points de reprise transmis par la copie primaire. Lors d’une panne de la copie primaire, une des copies secondaires la remplace et le traitement des messages reçus depuis la dernière sauvegarde est perdu.

La réplication semi-active

Cette technique permet un recouvrement de fautes plus rapide que la réplication passive. Les messages d’entrée sont traités par toutes les copies, mais une seule, le leader, fournit les messages de sortie. Pour mettre à jour leur état interne en l’absence de fautes, les autres répliques traitent directement les messages d’entrée, ou utilisent les « notifications » du leader. En cas de panne franche du leader une des copies peut ainsi prendre le relais sans perte.
La réplication passive est présentée par le projet Delta 4 [7] comme la technique la plus performante en cas d’absence de faute. La réplication active, exigeant la création de plusieurs processus, pourrait dégrader les communications réseau. La troisième catégorie intermédiaire, trouve un compromis pour gérer les événements non-déterministes. En effet, dans la réplication semi-active, le leader joue le rôle de synchronisation des messages internes. Les autres copies appelées suiveurs ne traitent les messages qu’après avoir reçu une notification de la part du leader.
D’autres types de réplication ont définis dans la littérature, comme la réplication semi-passive et la réplication coordinateur-cohorte [17].

Le recouvrement d’erreur

Le recouvrement d’erreur consiste à remplacer un état erroné par un état stable garantissant un système fonctionnel. Il existe deux techniques de recouvrement d’erreur:
• Le recouvrement par reprise : C’est une technique générale qui ramène le système à un « état correct sans erreur » qu’il occupait (Retour arrière). Elle nécessite la sauvegarde périodique de l’état du système sur support stable.
 Le recouvrement par poursuite : le système est ramené à un nouvel état « reconstitué », sans effectuer de retour arrière. La reconstitution n’est souvent que partielle. C’est une technique spécifique parce que la reconstitution d’état correct dépend de l’application et exige une analyse préalable des différents types d’erreurs possibles.
La Figure 5 illustre le recouvrement arrière. Un état stable, sauvegardé au cours de l’exécution des applications est appelé point de reprise (checkpoint). Périodiquement, un point de reprise est effectué et stocké sur un support stable, qui peut être un disque ou un serveur. En cas de défaillance, le système redémarre au point de reprise le plus récent. Il effectue ainsi un retour arrière depuis un point de reprise antérieur à la panne : ce qui constitue un gain en terme de temps d’exécution, puisse que les applications ne reprennent pas leur calcul à l’instant zéro.
Les deux mécanismes de recouvrement présentent des avantages et des inconvénients. La reprise, même si elle est la plus utilisée, peut être couteuse en temps et en espace de stockage. En effet, les phases de sauvegarde des points de reprise augmentent le temps de réponse des applications. En plus, les points de reprise occupent de la place selon le protocole exécuté dans le système. Son avantage est sa propriété générique, parce qu’elle s’adapte en générale à la plupart des architectures informatiques. La poursuite, quant à elle, présente un champ d’application limite. Étant spécifique, elle peut être efficace si les types d’erreurs possibles ont été listés antérieurement.
Dans la suite de ce document, nous ne traiterons que les mécanismes de tolérances aux fautes utilisant la technique du recouvrement arrière par reprise.

Problèmes liés au recouvrement arrière

Deux problèmes interviennent pour effectuer un recouvrement arrière: la cohérence d’état global et le déterminisme d’exécution.
L’état global d’un système réparti est l’ensemble des états locaux de tous les processus participants au fonctionnement de ce système. Il doit être cohérent pour garantir une exécution correspondant à un état possible du système.
Ensuite, le déterminisme d’exécution est une propriété des systèmes répartis qui indique la capacité de reproduire une exécution.
Nous allons voir dans les chapitres suivants les caractéristiques de ces problèmes liés à la reprise.

État global cohérent

Dans [8], l’état global d’un système est défini comme la collection des états locaux des processus et des canaux de communication qui les relient. L’état local d’un processus p est défini par son état initial et l’ensemble des événements ayant eu lieu sur p. Un état global cohérent est un état global intervenu lors d’une exécution correcte.
Cet état doit garantir la causalité des événements. L’ensemble des processus de la grille communiquant par passage de messages, l’état global cohérent doit assurer que l’événement d’émission d’un message m précède sa réception.
Un ensemble de points de reprise représentant un état global cohérent est appelé une ligne de recouvrement.
Un message orphelin est un message qui a été reçu sans être envoyé. Autrement dit, lors du calcul de la ligne de recouvrement, si la réception d’un message appartient à un des états locaux et son émission n’appartient pas à un de ces états, l’état global devient incohérent.
Sur la Figure 6.1, l’état global représenté par l’ensemble des points de reprise pr1, pr2 et pr3 est cohérent car aucun état local ne contient de message orphelin. Les messages m2 et m3 sont des messages en transit, ils sont envoyés, mais pas encore reçus.
La Figure 6.2 illustre un état incohérent. Si le processus 1 tombe en panne après envoi du message. L’état global formé par les états locaux pr1 et Z est incohérent car l’émission du message m n’appartient pas à l’état global. Le processus 2 est orphelin et doit faire un retour vers le point de reprise pr2 pour supprimer le message orphelin et assurer la cohérence du système. La suppression des messages orphelins peut donc entraîner un effet domino avec des reprises en cascade.

Déterminisme d’exécution

Un événement est déterministe si et seulement si plusieurs exécutions de cet événement à partir du même état initial donnent le même état final.
Le déterminisme d’exécution est basé sur l’hypothèse PWD (Piecewise Deterministic Assumption) définie par Strom et Yemini [9] et qui dit :
• un processus peut être modélisé comme un intervalle d’état
• chaque intervalle d’état débute par un événement non-déterministe
• l’exécution durant chaque intervalle d’états est déterministe
En effet, durant l’exécution sans panne, les processus sauvegardent dans leur journal les événements non-déterministes. Ils correspondent aux réceptions de messages ou aux événements internes au processus.
En cas de panne, le processus défaillant fait un retour arrière sur le dernier point de reprise et utilise son journal pour rejouer les événements non-déterministes. L’hypothèse PWD garantit que la réexécution aboutira au même état final.
Un problème survient lorsqu’un événement non-déterministe apparaît dans un intervalle état, par exemple si l’on ne dispose pas de ses caractéristiques. Dans ce cas les protocoles de journalisation des messages ne seront pas utilisés.

Les protocoles de points de reprise

Par définition, un point de reprise (checkpoint) est la sauvegarde de l’état d’un processus à un instant donné, sur un support de stockage stable. Un support stable est un espace de stockage accessible par toutes les applications utilisées dans la grille disposant des droits suffisants, et protégé contre toute sorte de pannes. Il est souvent représenté par un serveur de stockage.
Les protocoles basés sur les points de reprise permettent de faire des sauvegardes périodiques de l’ensemble des états des processus. Pendant le recouvrement, les points de reprises les plus récents sont restaurés pour reproduire un état global cohérent du système avant la panne (Figure 4).
La tolérance aux fautes par recouvrement arrière se base sur les protocoles de points de reprise pour éviter la perte de temps de calcul dans les environnements de calcul haute performance comme les grilles. Il existe différentes catégories de protocoles de points de reprise classés selon la méthode utilisée pour effectuer la sauvegarde :
• Les protocoles de points de reprise coordonnés
• Les protocoles de points de reprise non-coordonnés
• Les protocoles de points de reprise induits par les communications.

Points de reprise coordonnés

Ce protocole exige aux processus de coordonner l’établissement de leurs points de reprise pour former un état global cohérent. L’algorithme bloquant se déroule ainsi [10] (Figure 7):
• Les communications sont bloquées pendant l’établissement des points de reprise.
• Un coordinateur fait un point de reprise et diffuse un message ‘checkpoint-request’ à tous les processus pour initier une phase de sauvegarde.
• Quand un processus reçoit ce message, il arrête son exécution et vide ses canaux de communication, fait une tentative de point de reprise et envoie un accusé de réception au coordinateur.
• Après avoir reçu l’accusé de réception de tous les processus, le coordinateur diffuse un message ‘commit’ à tous les processus pour leur ordonner de faire un point de reprise.
• Chaque processus supprime ainsi l’ancien point de reprise, et sauvegarde son état. Le processus est maintenant libre de terminer son exécution et d’échanger des messages avec les autres processus du système.
Cette approche simplifie le recouvrement et évite l’effet domino, puisque chaque processus redémarre toujours au point de reprise le plus récent. Aussi, le protocole exige à chaque processus de maintenir un seul point de reprise permanent en mémoire stable, ce qui réduit le surcoût dû au stockage ainsi que la nécessité d’avoir un algorithme de récupération des points de reprise (garbage collection) [10]. En pratique, le protocole coordonné est facile à implémenter. Par exemple, CoCheck [23], le mécanisme assurant la cohérence des états dans Condor [24] est basé sur le protocole de Chandy & Lamport [12].
Son principal inconvénient est cependant la large latence introduite par la coordination des processus participants. Pour améliorer les performances de la sauvegarde coordonnée, plusieurs techniques ont été proposées :
• Point de reprise coordonné non-bloquant : le plus connu est celui de Chandy et Lamport [12]. Il fonctionne sous l’hypothèse des canaux FIFO (First In First Out ; premier arrivé, premier servi), en utilisant des marqueurs. En effet, lors de la sauvegarde des points de reprise, chaque processus enregistre son état local et envoie sur tous ses canaux de sortie un marqueur pour informer les autres processus voisins qu’il a effectué un point de reprise. À la réception de ce marqueur, un processus recevant ce message pour la première fois sauvegarde à son tour son état et diffuse le marqueur, et ainsi de suite.
• Point de reprise coordonné minimale : Koo et Toueg [13] propose un protocole coordonné minimal, qui ne fait intervenir que les processus ayant participé à la dernière sauvegarde. Seuls les processus susceptibles de créer une incohérence en cas de reprise sauvegardent leur état. L’algorithme se déroule en deux phases. Durant la première phase, l’initiateur identifie tous les processus dont il a reçu un message depuis le dernier point de reprise, et leur envoie une demande, le message étant un orphelin potentiel. Sur réception de la demande, chaque processus identifie à son tour tous les processus pouvant créer des messages orphelins et leur envoie aussi une demande, jusqu’à ce que tous les processus soient identifiés. Après l’identification des processus, la deuxième phase correspondant à la sauvegarde des états locaux proprement dite.
• Point de reprise coordonné avec horloge de synchronisation : Dans [14] [15], les auteurs utilisent des horloges de synchronisation pour effectuer des points de reprise locaux au niveau de tous les processus participants, et approximativement au même moment sans un initiateur. Le protocole assure qu’aucun message n’est échangé durant la sauvegarde.

Points de reprise indépendants

Ce protocole évite la phase de synchronisation en laissant à chaque processus l’autonomie de sauvegarder son état local (Figure 8). L’avantage de cette autonomie est que chaque processus pourra sauvegarder son état au moment opportun, par exemple si la quantité d’information est minimale. Ce qui réduit le surcoût du stockage en termes de quantité d’information à sauvegarder. Dans [10], les étapes du recouvrement sont [10]:
• Le processus de récupération entame un retour arrière par la diffusion d’un message de ‘dependancy-request’ pour rassembler les ‘informations de dépendance’ maintenues par chaque processus
• Quand un processus reçoit ce message, il arrête son exécution et envoie les informations de dépendances enregistrées sur la mémoire stable
• L’initiateur calcule la ligne de recouvrement basée sur les ‘informations de dépendance’ globales et diffuse un message de ‘rollback request’ contenant la ligne de recouvrement.
• Sur réception de ce message, chaque processus appartenant à la ligne de recouvrement reprend son exécution, sinon il revient au point de reprise précédent, celui indiqué par la ligne de recouvrement (Figure 8).
La dernière étape de l’algorithme peut causer l’effet domino, qui peut engendrer une perte du travail réalisé avant la panne et la sauvegarde inutile de points de reprise qui ne feront jamais partie d’un état global cohérent. Le protocole non coordonné fait revenir en arrière le processus concerné par la panne, ainsi que ceux qui en dépendent causalement. Il oblige aussi chaque processus à maintenir plusieurs points de reprise.

Points de reprise induits par les communications

Ce protocole (CIC: Communication Induced Checkpointing) définit deux types de points de reprise [41][42]:
• Des points de reprise locaux pris par les processus de manière indépendante, pour éviter la synchronisation de la sauvegarde coordonnée
• Des points de reprise forcés en fonction des messages reçus et envoyés et des informations de dépendance estampillées sur ces messages, pour ainsi éviter l’effet domino de la sauvegarde non coordonnée, garantir l’avancement de la ligne de recouvrement.
À l’opposé des protocoles de point de reprise coordonné, le surcoût dû à l’accès au support stable disparaît parce que le protocole CIC ne nécessite aucun échange de message pour forcer un point de reprise. En effet, il utilise la technique utilisée par la journalisation causale en insérant la signalisation sur les messages échangés.
Le protocole de Xu et Netzer [42] repose sur les notions de Z-chemin et de Z-cycle. Ces notions permettent de déterminer si une sauvegarde sera utile ou non en cas de panne et de reprise. Un Z-chemin est une séquence de messages qui connecte deux points de reprise et un Z-cycle est un Z-chemin qui boucle c’est à dire il commence et se termine par le même point de reprise. Pour forcer un point de reprise, le protocole CIC vérifie que le point de reprise n’appartient pas à un Z-cycle. Les techniques de sauvegarde de point de reprise induit par les communications peuvent être classées en deux catégories :
− Model-based coordination : elle repose sur la prévention des modes de communication et de points de reprise qui pourraient entrainer des Z-cycles. Ces modèles sont conçus pour détecter la formation de ces Z-cycles qui pourraient se former au cours de l’exécution des applications [42].
− Index-based coordination : cette catégorie utilise les horloges logiques. En effet, ces horloges sont ajoutées aux messages afin de savoir à quel moment il faut sauvegarder un point de reprise [42].
Même si les protocoles CIC trouvent un compromis entre la sauvegarde coordonnée et la sauvegarde indépendante, elles présentent des inconvénients liés à la fréquence de sauvegarde des points de reprise forcés. Comme les points de reprise augmentent le temps d’exécution des applications dans les grilles, il serait mieux de réduire leurs nombres pour éviter la dégradation des performances du système. Malheureusement, une évaluation de ce type de protocoles a montré que le nombre de points reprise forcé était souvent élevé pour certains modèles d’application [41].

Les protocoles de journalisation

Depuis plusieurs décennies, la journalisation des messages a été une technique très utilisée pour assurer la tolérance aux pannes dans les systèmes répartis. Les protocoles de journalisation nécessitent la sauvegarde périodique des états locaux des processus, et l’enregistrement sur support stable de tous les messages reçus après l’établissement des points de reprise locaux.
En cas de panne d’un processus, il est relancé à partir du dernier point de reprise, et tous les messages reçus après ce dernier lui sont renvoyés dans l’ordre où ils ont été initialement reçus. Tous les protocoles de journalisation des messages exigent que l’état d’un processus récupérable soit toujours compatible avec l’état des autres processus. Ils doivent ainsi garantir l’absence du processus orphelin, qui rendent le calcul de l’état global incohérent.
Il existe trois catégories de journalisation de messages : optimiste, pessimiste, causale. Elles différent de par leur technique de sauvegarde, de recouvrement, de récupération de point de reprise (garbage collection) et de leur surcoût induit durant l’exécution sans faute [16].

Journalisation optimiste

Ce protocole utilise l’hypothèse selon laquelle la journalisation d’un message sur support fiable sera complète avant qu’une panne ne se produise. En effet, au cours de l’exécution des processus, les déterminants des messages, à savoir leur contenu et identifiants, sont conservés en mémoire volatile avant d’être périodiquement vidés sur support stable. Le stockage sur mémoire stable se fait de manière asynchrone : le protocole n’exige pas le blocage de l’application pendant la sauvegarde sur mémoire stable. La latence induite est alors très faible.
Cependant une panne peut survenir avant que les messages ne soient enregistrés sur mémoire stable. Dans ce cas, les informations sauvegardées en mémoire volatile du processus en panne sont alors perdues. Le recouvrement devient compliqué puisque tous les processus ayant reçu un message provenant du processus défaillant deviennent orphelins (Figure 9). Ce qui peut produire l’effet domino. En plus, le protocole est obligé de maintenir plusieurs points de reprise en mémoire. La récupération des points de reprise devient plus complexe. Le calcul pour obtenir un état global cohérent peut avoir un coût important parce que les processus peuvent être amenés à redémarrer au point de reprise qui n’est pas le plus récent.
Pour éviter l’effet domino, le protocole enregistre les informations de dépendances entre les messages durant l’exécution sans faute. Une solution consiste à utiliser des vecteurs de dépendances attaché aux messages et dont la taille est égale au nombre total de processus. Mais cela est très coûteuse pour les grands systèmes comportant un nombre important de processus.

Table des matières

Chapitre I : Introduction
1. Problématique
2. Contributions
3. Organisation du manuscrit
Chapitre II : Etat de l’art
1. Introduction
2. Tolérance aux fautes dans les grilles informatiques
2.1. Les grilles informatiques
2.2. Notion de tolérance aux fautes
2.3. Techniques de tolérance aux fautes dans les grilles
3. Problèmes liés au recouvrement arrière
3.1. Etat global cohérent
3.2. Déterminisme d’exécution
4. Les protocoles de points de reprise
4.1. Points de reprise coordonnés
4.2. Points de reprise indépendants
4.3. Points de reprise induits par les communications
5. Les protocoles de journalisation
5.1. Journalisation optimiste
5.2. Journalisation pessimiste
5.3. Journalisation causale
6. Protocoles hiérarchiques basés sur les points de reprise et journalisation
7. Conclusion
Chapitre III : Etude comparative des mécanismes de recouvrement arrière
1. Introduction
2. Analyse comparative
2.1. Comparaison des protocoles de points de reprise
2.1.1. Le surcoût engendré durant l’exécution sans faute
2.1.2. Le surcoût du recouvrement
2.1.3. L’utilisation du support de stockage stable
2.1.4. La résistance aux effets domino et messages orphelins
2.2. Comparaison des protocoles de Journalisation
2.2.1. Le surcoût durant l’exécution
2.2.2. L’utilisation du support de stockage stable
2.2.3. Les performances durant le recouvrement
2.3. Synthèse
3. Algorithmes hiérarchiques
3.1. Modèle du système
3.2. Protocoles hiérarchiques
3.2.1. Point de reprise coordonné
3.2.2. Journalisation optimiste
4. Evaluation de performance
4.1. Architectures simulées
4.1.1. Modèles d’application
4.1.1.1. Diffusion de messages
4.1.1.2. Application en Jeton
4.2. Environnement de simulation
4.2.1. Configuration des réseaux
4.2.2. Implémentation des protocoles de tolérance aux fautes
4.3. Evaluation
4.3.1. Exécution sans faute
4.3.2. Nombre de processus à redémarrer
4.3.3. Performance durant le recouvrement
4.3.4. Impact de l’hétérogénéité des clusters
5. Conclusion
Chapitre)IV:)Composition)d’algorithmes)de)point)de)reprise)dans);les)architectures)hiérarchiques)
1. Introduction
2. Protocoles de sauvegarde
2.1. Point de reprise coordonné non bloquant de Chandy et Lamport
2.2. Journalisation pessimiste basée sur l’émetteur
3. Description des combinaisons de protocoles
3.1. « CLML »
3.2. « MLCL »
3.3. « MLML »
3.4. « CLCL »
4. Evaluation de performance
4.1. Modèle d’application
4.2. Exécution sans faute
4.3. Exécution avec injection de fautes
4.4. Impact de la clusterisation sur le nombre de marqueurs
5. Conclusion
Chapitre V: Un nouveau protocole hiérarchique adaptatif par points de reprise et journalisation
1. Introduction
2. Description du protocole
3. Implémentation du protocole
3.1. Principe
3.2. Détails de l’implémentation
3.3. Recouvrement
4. Evaluation des performances
4.1. Comparaison entre le protocole adaptif, « MLML » et « MLCL »
4.2. Taille des messages
4.3. Nombre de processus à redémarrer
4.4. Impact de la journalisation
5. Conclusion
Chapitre VI: Conclusion
Conclusion
Perspectives
Références
Annexe 1

Télécharger le rapport complet