Scribd
Importer
31 vues19 pages

SD

je voudrais télécharger ce livre

Transféré par

Souhaila Djaffal
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
31 vues19 pages

SD

je voudrais télécharger ce livre

Transféré par

Souhaila Djaffal
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Muted RSS & Aptis Dee DETERMINATION D’UN ETAT GLOBAL COHERENT 1. Introduetion L’observation d’un état global permet * de détecter des propriétés caractérisant I’exécution (terminaison, interblocage, vérification d’assertions, etc.) © @effectuer des mesures de performances «de capter des états pouvant servir de points de reprise en cas de défaillance Mais il est Difficile d’effectuer une observation globale dans un contexte réparti A cause de : > pas d’horloge commune - > temps de transfert des messages non bomeé (fini si pas de perte) > impossible d’effectuer une observation simultanée par exemple : des photographies des vols d’oiseaux L’objectif de cette partie est la détermination d’un état global cohérent qui peut étre observé. Cet état est constitué des états locaux des sites et des canaux de communication. 2. Etat global 2.1. Définitions Chaque processus et chaque canal posséde 4 tout moment un état local : Y état local el; d’un processus P; résulte de son état initial et de la séquence événements dont ce processus a été le sige. Y Pétat ecy d’un canal cyest I’ensemble des messages en transit sur ce canal, c’est a dire qui ont été émis par le processus Pi et n’ont pas encore été regus par le processus Pj. Chaque événement met en jeu un processus et éventuellement un canal. On distingue : + Evénement interne sur P, : provoque la transition de el; a el;’, états avant et aprés T'événement capri casa + Emission de m pat P; sur cy (cet événement est noté émission{m)) qui provoque : la cy U {m) + Réception de m pat P; sur cy (cet événement est noté réception(m)) qui provoque : 1a transition de el; & el,’ et l'affectation ecy transition de el, & eli et l’affectation ecfi := eqji\ {m}. Chacun de ces événements est supposé atomique Formellement, un état global cohérent est tel que : i) elyest un état local du processus P; ii) Les conditions C/ et C2 suivantes sont vérifiées: > Cl): si Pévénement émission, (m) est capté dans ef, alors l’événement réception; (m) est soit capté dans el, soit le message m appartient & ecy > C2): si Pévénement émission; (m) n’est pas capté dans el; ,’vénement réceptiony (rm) n’est pas non plus capté dans ely Un état global cohérent est aussi appelé “coupe cohérente” (« consistent cut»). ‘Exemple : Fi pte net | ge ae a AN aw Figure 1. Un graphe de communication. el, P, Py ay a, i _ Mo Tit mg el, Py Figure 2. Une exécution répartie. 1.2 Définition équivalente d’une coupure cohérente Une coupure C de histoire globale d’un systéme est un n-uplet dont chaque composante est un préfixe de histoire locale du site correspondant : CHK ety oney Gj y vee Cn > OD |= _ Une coupure C est dite eohérente (ou consistante) si elle est fermée vis & vis du passé de ses éléments : tout élément dans le passé d’un événement de la coupure appartient Iui-méme a la coupure. Exercice Dans I’exemple suivant, les coupures C et C’ sont-elles cohérentes ? ? a 1.3. Caractérisation des coupures cohérentes par estampillage vectoriel de Lamport On associe & une coupure C Ia suite des événements (6 est ’événement le plus récent du site S; appartenant a la coupure). Associons 4 la coupure C Iestampille vectorielle EV(C) définie par : EV(C) = . La coupure est cohérente si et seulement si: EV(C) = sup (BV(e1), ... EV(@j),... EV(En)), avec : sup EV(e1), ... EV(G),--» EV(en)) [k] = (sup (EV(e1) [X), .-- sup (EV() [K], «.. sup EV (en) Ek] Exercice : appliquer ce résultat aux coupures C et C’ de l'exemple précédent. 3 3. Hypotheses sur les canaux de communication 3.1, Définition des types de messages Soit un canal, m et m1 deux messages empruntant ce canal. On dit que m double mI si et seulement si : Emission (m1) —> émission (m) et réception (m) > réception (ml) Quatre types possibles de messages peuvent étre définis selon les contraintes de doublement : i) Un message m est de type marqueur s'il ne peut ni doubler ni étre doublé par aucun message transitant sur le méme canal : Ci ml, émission (ml) —> émission (m) => réception (ml) — réception (m) et Om2, émission (m) > émission (m2) => réception (m) —» réception (m2) marque Pp arg my ™ 7] > Figure 3. Livraison d’un marqueur. ii) Un message m est de type ct_passé (contraint par son passé) sil ne peut doubler aucun message : (I ml, émission (ml) — émission (m) => réception (ml) —> réception (m) ctpassé =m: > 2 my % Figure 4. Livraison d’un message contraint par son passé. (tous les messages émis avant lui sont recus avant lui) iii) Un message m est de type ef futur (contraint par son futur) s'il ne peut étre doublé par aucun message : (I m2, émission (m)—> émission (m2) => réception (m) > réception (m2). fe mm, ct-futur m) Figure 5. Livraison d’un message contraint par son futur. (tous Tes messages énts apris hit seront recus aprés lad) iv) Un message m de type ordinaire n’impose pas de conditions de réception : * ine peut pas doubler les messages marqueur et ct futur * ile peut pas étre doublé par les messages marqueur et ct_passé Les types de messages définissent une gamme de comportement du canal : * lemoins contraint (tous les messages sont ordinaires) * Ie plus contraint (tous les messages sont de type marqueur) => canal FIFO Pour un canal donné, les trois propriétés Al, A2 et A3 suivantes sont équivalentes : © AI: tous les messages sont de type ct_passé © A2: tous les messages sont de type ct_futur © A3: tous les messages sont de type marqueur 3.2. Hypothises globales sur Jes canaux de communication La propriété d’ordre causal porte sur l'ensemble des canaux. O Py, Py, Pk, Om émis sur Cy , Om émis sur Cy: Emission, (m) — Emission, (ml) => réception, (m) — réception; (ml) ~ my Figure 6, Réception non causale. 5 Remarque : si la propriété d’ordre causal est garantie alors chaque canal a un comportement FIFO (réciproque fausse). ° 3.3. Superposition “ ‘A chaque processus P; est associé un processus observateur CTL;. Ce processus peut lire I’état de P;, La réception d’un message par P; est réalisée par CTL;, qui le délivre ensuite & Pj - Pi confie CTL; les messages qu’il veut transmettre vers tout autre processus Pj. Les processus CTL; sont charges de capter un état global cohérent de l’application et ils coopérent entre eux &Paide de messages de contréle. Un ‘els schéma dobservation des processus P; par des contréleurs CTL; est appelé superposition. 4, Algorithme de Chandy et Lamport . 4.1. Principe du fonctionnement : Chaque processus P; enregistre son état local el; et I’état de ses canaux entrants en observant Jes deux régles suivantes : RI : un processus Pj qui capte son état local envoie sur tous ses canaux de sortie un message de contréle (appelé mk) pour signifier & ses voisins qu’il a enregistré son état local. R2: Ala réception d’un message mk sur un de ses canaux d’entrée, par exemple cj , un processus P; peut se trouver dans l'une des deux situations suivantes : © Pyn’a pas encore capté son état local : il doit alors enregistrer cet état (R1) > Pétat ecy du canal oy est vide car Pj a regu tous les messages émis avant le message mk. o Pad réception antérieure d’un message mk sur un autre canal d’entrée) =?1’état du enregistré son état local (soit de sa propre initiative, soit suite & une canal cy est constitué des messages regus sur. ce canal aprés que Pj ait enregistré son état local et avant qu’il ne regoive mk. 4.2. Exemple de fonctionnement de Valgorithme de Chandy et Lamport #le site enregistre son état —> marqueur —> message enregistré >_ —— la coupure correspondante ci Al a a ati i cS aa os: Ngo Desh itn’ M2. asd part < (03D CHAPITRE 03 : Problémes d’accord SOMMAIRE 1. Introductions... 2. Des problémes d’accord : 2.1 La diffusion atomique : 2.2 La validation atomique 2.3 U'élection d’un leader : 3. Une brique de base : le consensus 3.1 Le consensus :... Ob ew NNN 3.2 Le consensus probabiliste : 3.3 Le consensus uniforme : 3.4 Le consensus ensembliste (le k-consensus) 4, Le résultat de FLP : 5. Contourner le résultat d'impossibilité de FLP : 6, Les détecteurs de défaillances non fiables :. 6.1 Propriétés : 6.2 Classification 7. Résolution du consensus en utilisant des détecteurs non fiables. ev i CHAPITRE 03 : Problémes d’accord 1. Introduction: La mise en ceuvre et la gestion d’un systéme réparti sont devenues une tache difficile et compliquée. Cette difficulté résulte de plusieurs problémes, _parmi la ceux-c synchronisation, l'ordre des événements, allocation de ressources, la reconfiguration, etc. Beaucoup de taches se fondent sur ’accord des entités distribuées, le consensus est une forme abstraite des problémes d’accord qui est sujet 4 des recherches intensives. Les protocoles d’accord sont au coeur de nombreux systémes distribués et applications, ils sont utilisés comme un moyen pour assurer la coordination des entités distribuées. La coordination est essentielle pour construire un état cohérent et pour assurer une évolution, cohérente du systéme. Les protocoles d'accord peuvent étre utilisé A différents niveaux du systéme et pour une variété d’objectifs, Ceux-ci peuvent s'étendre sur des services de base d'un systéme tels que I’établissement de ordre total de l’exécution des primitives de communication, la gestion de groupes, la diffusion atomique, la validation atomique d’une transaction, I’élection d’un leader, et la synchronisation de 'horloge. Dans ce chapitre, nous présentons quelques problémes d'accord..Par la suite, nous donnons quelques résultats de recherches existants sur la solvabilité du consensus. Nous présentons également la notion d’un détecteur de défaillances et ses caractéristiques. Nous présentons aussi quelques autres classes de détecteurs de défaillances. 2. Des problémes d’accord : ‘Nous décrivons dans cette section quatre exemples de problémes d’accord : la diffusion atomique, la validation atomique, I’élection d’un leader et la gestion de groupes. La résolution {Ph Pas Pa} de ce type de probléme nécessite un accord d’un ensemble de » processus II 2.1 La diffusion atomique : La diffusion atomique est un paradigme trés important dans les systémes distribués tolérant aux fautes. Informellement, la diffusion atomique exige que tous les processus corrects délivrent le méme ensemble de messages dans le méme ordre. Formellement, La diffusion atomique est une diffusion fiable qui satisfait : © Ordre total : si deux processus corrects p et q délivrent deux messages m et m’, alors p délivre m avant m’ si 4 seulement si q délivre m avant m’. La diffusion atomique peut étre également définie par les \q propriétés suivantes : © Terminaison : Si un processus correct diffuse un message m, alors tous les processus corrects délivrent ce message. CHAPITRE 03 : Problémes d’accord © Validité : Si un processus délivre un message m, alors ma été diffusé par au moins un processus. © Intégrité : un processus remis un message m au plus une fois ; * Accord : Si un processus correct délivre un message m alors tous les processus corrects délivrent m ; © Ordre i un processus correct délivre un message m avant un message m’, alors tous les processus corrects délivrent m avant m’ Chandra et Toueg [1996] ont montré que le consensus et la diffusion atomique sont deux problémes équivalents. En d'autres termes une solution a l'un implique automatiquement une solution 4 l'autre. Informellement une utilisation du consensus pour résoudre la diffusion atomique consiste 4 effectuer une décision sur les messages a délivrer, et sur ordre de ces messages. Par ailleurs, pour résoudre le consensus nous pouvons utiliser la diffusion atomique de la fagon suivante : pour décider d’une valeur, un processus la diffuse de fagon atomique. Pour décider d’une valeur un processus prend la valeur du premier message qu’il a délivré. Par la proprigté d’ordre total de la diffusion atomique tous les” ~ processus corrects vont délivrer le méme message. 2.2 La validation atomique : Dans un systéme réparti oi les processus coopérent par transactions, un probléme accord doit étre résolu entre les processus. Ce probléme, appelé validation atomique (AC pour Atomic Commitment), améne les processus se mettre d’accord sur le résultat d’une transaction : commit (validation) ou abort (annulation). Plus formellement, la validation atomique est définie par les cing propriétés suivantes : ~ Unanimité : deux processus ne peuvent décider dififéremment ; = Validité : la transaction n’est valide que si tous les processus votent oui ; = Terminaison : si toutes les défaillance sont réparées et aucune défaillance ne survient, tous les processus doivent décider ; = _Non-Trivialité : les processus doivent décider de valider si tous les votes sont oui et si aucun processus n’est défaillant ou suspecté d’étre défaillant ; - Non-Blocage: tout processus correct décide et si certains processus sont défaillants, les autres doivent décider de la terminaison. Lorsqu’il est demandé que tous les processus corrects finissent par décider en dépit de défaillances dautres processus le probléme est indiqué sous le nom de validation atomique non bloquante (NBAC pour Non-Blocking Atomic Commitment) CHAPITRE 03 : Problémes d’accord Deux protocoles sont utilisés, le 2PC (Two-Phase Commit) et le 3PC (Three-Phase Commit). Le premier pour résoudre AC et le deuxigme pour résoudre NBAC dans les systémes synchrones. Guerraoui [1995] a montré que NBWAC (Non-Blocking Weak Atomic Commitment) est réductible au consensus uniforme (qui est réductible au consensus). Le NBAC implique que la décision est commit si tous les processus votent oui et s'il n’y a pas de processus défaillants. Le NBWAC implique que la décision est commit si tous les processus votent oui et si aucun processus n’est suspects. 2.3 L’élection d’un leader : Dans le probléme d’élection dun leader, tout moment, au plus un processus se considére comme le leader et un nouveau leader doit étre élu si le leader tombe en panne. Pour déterminer plus précisément la notion de coordonnateur (leadership), nous supposons que chaque processus a une copie locale dune variable distribuée, dénotée par leader. La copie de leader pour un processus p, est dénotée par leader, et pour n’importe quel processus p, , faws}. a Nous disons qu’un processus p; est le /eader & instant ¢, si pin’est pas défaillant & Vinstant ¢ leaderpie {vr et _leadery = vrai, Formellement, nous définissons le probléme d’élection dun leader par les deux proprigtés suivantes : * Accord : 4 l’instant t il existe un seul processus leader (deux processus ne peuvent pas étre leader en méme temps). © Terminaison : & tout moment, il existe finalement un leader. Sabel et Marzullo [1995] ont prouvé que le probléme d’élection d’un leader est réductible au probléme de consensus. Informellement, une utilisation du consensus pour résoudre I’élection d'un leader consiste a effectuer une décision sur le leader a élire. 3. Une brique de base : le consensus Le consensus constitue une base pour la résolution des problémes d’accord. Une résolution pour le consensus implique un élément essentiel pour la résolution des problémes accord. Nous décrivons dans cette section le problémes de consensus, puis certaines variantes de ce probléme : le consensus probabiliste, le consensus uniforme, et le consensus ensemblistes. CHAPITRE 03 : Problémes d’accord 3.1 Le consensus : Dans le probléme de consensus, chaque processus correct propose une valeur vj, et tous les processus corrects doivent atteindre une décision unanime et irrévocable sur une valeur v. Cette valeur doit avoir été proposée par au moins un processus participant au consensus. Nous implémentons le consensus par l'usage de deux primitives, propose(v) et décide(v). Quand un processus exécute propose(v), on dit qu’il propose v ; similairement, quand un processus exécute décide(v), on dit qu’il décide sur v. Formellement, le probleme de consensus est défini par les trois propriétés suivantes : © Terminaison : tout processus doit finir par décider ; © Validité : si un processus décide une valeur v, alors v a été proposée par au moins un processus ; * Accord : deux processus ne peuvent décider différemment. 3.2 Le consensus probabiliste : Pour affaiblir la propriété de terminaison qui ne peut pas étre garantie dans un systéme réparti, Ben-Or [1983] a proposé le consensus probabiliste. Le consensus probabiliste différe du consensus par la propriété de terminaison. Formellement, la propriété de terminaison dans le consensus probabiliste, appelée R-terminaison (Random-termination), est définit comme suit ‘© R-terminaison : tous les processus corrects décident avec une probabilité égale & 1. Le consensus probabiliste ne garantit pas la terminaison d’un processus correct, mais la probabilité de terminaison converge vers le 1 aprés une infinité de ronde. 3.3 Le consensus uniforme : Dans a définition du consensus, les processus défaillants peuvent décidé différemment des processus corrects, cette définition ne convient pas certaines applications qui demandent un niveau de sfreté trés élevé. Pour interdire ce défaut, le consensus uniforme a té défini et se différe du consensus de base par la propriété d’accord : * Accord uniforme : Si un processus décide une valeur vy, alors tous les processus décident v. Le probléme de consensus uniforme est plus difficile a résoudre que le consensus, et il n’a aucun sens dans les systémes sujet a fautes arbitraires. CHAPITRE 03 : Problémes d’accord 3.4 Le consensus ensembliste (le k-consensus) : Pour une tolérance aux défaillances fortes, Chadauri [1990] a introduit le k-consensus pour affaiblir la propriété d’accord. Le k-consensus autorise la décision sur au plus & valeurs . Dans le consensus ensembliste la propriété d’accord est remplacée par : + K-accord : il existe au plus k valeurs différentes décidées par les processus. Ce probléme est plus faible que le consensus standard (plus que k est grand plus que le probléme est faible). Une solution pour le k-consensus est une solution pour le (k+1)-consensus. Par conséquent, une solution au consensus (le 1-consensus) est aussi une solution pour le k-consensus. La difficulté de ce probléme dépend de la valeur de k : - pour k f: Palgorithme de résolution de probléme est simple, quand un processus regoit une valeur diffusée par k processus, il décide cette valeur. 4. Le résultat de FLP : . - La spécification de probléme du consensus, présentée dans la section précédente, peut ire implémentée dans les deux modéles de systémes principaux : les syst#mes synchrones et les systémes asynchrones. Cependant, dans un systéme asynchrone, dune part le consensus est facile & concevoir, et d’autre part il est difficile 4 résoudre en présence de défaillance. Un résultat d’impossibilité de consensus dans un systéme réparti asynchrone est défini par Fisher, Lynch et Paterson [1985]. En effet, ce résultat montre qu’un consensus n’est pas réalisable de fagon déterministe dans un systéme asynchrone soumis a des crashes de processus, méme si le systéme n'est soumis qu’a une seule défaillance et que les canaux sont fiables. De maniére intuitive, ce résultat d’impossibilité est justifié par le fait qu’il est impossible de distinguer un processus lent d’un processus en panne, lorsque l'on ignore les vitesses d’exécution des processus et les délais de transmission des messages. Ainsi, une des principales difficultés rencontrées dans le domaine de Valgorithmique distribuée tolérante aux fautes conceme ce résultat d’impossibilité dans un environnement asynchrone puisqu’il empéche la résolution de nombreux problémes d’accord dans de tels environnements. Cependant, différentes alternatives permettent de contourer cette impossibilité. CHAPITRE 03 : Problémes d’accord 5. Contourner le résultat d’impossibilité de FLP : Pour contourner le résultat d’impossibilité de FLP , nombreuses recherches ont été réalisées dans le domaine de I’algorithmique distribuée, afin de permettre la résolution du probléme du consensus dans un systéme asynchrone dans lequel les processus peuvent étre soumis a des défaillances franches. (é considérées pour palier a ce probléme fondamental : Diverses approches ont ainsi * La définition de problémes affaiblis et leurs solutions. Par exemple, le cas avec le probléme du K-consensus [1990] qui a été défini pour affaiblir la propriété d’accord et pour faciliter la résolution du consensus. © La résolution du consensus est également possible dans un environnement partiellement synchrone, tel que le systéme défini par Dwork et al [1988]. © Une approche élégante a été développée par Chandra et Toueg [1996], & savoir enrichir le systéme par un mécanisme de détection de défaillances non fiable, appelé détecteurs de défaillances non fiables. Plusieurs travaux ont été menés autour de cette approche de résolution du consensus. © Une autre approche récente a été proposée par Mostéfaoui et al [2003], appelée approche contrainte par conditions. Elle est basée sur identification des conditions, relatives aux valeurs proposables, autorisant une décision directe des processus. © ete, 6. Les détecteurs de défaillances non fiables : Une alternative élégante, pour contourner la non résolution du consensus dans les systémes répartis asynchrones, a été proposée par Chandra et Toueg [1996]. Cette alternative basée sur ’idée d’augmentation du modéle de calculs répartis asynchrone avec un modéle un mécanisme exteme de détection de défaillances qui peut faire des erreurs. En particulier, ce mécanisme spécifie le concept de détecteur de défaillance non fiable pour un systéme réparti asynchrone avec des défaillances par arrét définitif. Informellement, un détecteur de défaillances non fiable est ou FD-Oracle est un ensemble de modules distribués qui fournissent (pos iblement incorrecte) aux processus du systéme une liste de processus suspectés d’étre défaillants. Chaque processus a ’accés 4 un module local de détecteur de défaillances qui contrdle les autres processus dans le systéme, et maintient Ia liste des processus suspectés d’étre défaillants. Cette liste peut étre différente dun processus 4 l’autre. Un module de détecteur de défaillances peut faire des erreurs par la 7 CHAPITRE 03 : Problémes d’ accord non suspicion d’un processus crashé ou par l’ajout erroné d’un processus correct & la liste des processus suspectés, c.-d-d., il peut suspecter qu’un processus p est crashé bien que p fonctionne encore. S'il estime plus tard que p est suspecté incorrectement, il peut enlever p de sa liste de processus suspectés. Ainsi, chaque module peut ajouter ou enlever & maintes reprises des processus de sa liste des processus suspectés. Formellement, un détecteur de défaillances est caractérisé par deux propriétés abstraites : Ja complétude et la précision. En général, la complétude exige qu'un détecteur de défaillances doit suspecter tous les processus défaillants, tandis que la précision restreint les erreurs (suspections erronées) qu’un détecteur de défaillances peut faire: Chandra et Toueg ont défini deux propriétés de complétude et quatre de précision, lesquelles sont combinées pour engendrer huit classes de détecteurs de défaillances. Ils ont montré aussi que le probleme du consensus peut étre résolu avec n’importe quelle classe de ceux-ci. Module Figure 1. Systéme enrichi d’un détecteur dé défaillances 6.1 Propriétés : Chandra et Toueg ont spécit un détecteur de défaillances en termes de deux propriétés abstraites qui doivent étre satisfaites : Ja complétude et la précision. Ces deux propriétés sont utilisées comme une base pour la conception des implémentations pour les détecteurs de deéfaillances et pour prouver la correction de ces implémentations. - La complétude : Nous considérons deux propriétés de complétude suivantes : CHAPITRE 03 : Problémes d’accord ° Complétude forte: tous les processus défaillants finiront par étre suspectés définitivement par tous les processus corrects. Formellement un détecteur de défaillances D satisfait la complétude forte si VF,WH € D(F),3t €T,p € crashed(F),Wq € correct(F),W1'>t: pe H(q.t') Complétude faible : tous les processus défaillants finiront par étre suspectés. par au moins un processus correct. Formellement un détecteur de défaillances D satisfait la complétude faible si: VF,WH € D(F),3t € T,Vp € crashed (F),3q € correct(F),Wt'2 t: pe H(qg.t') Tel que : F:; dénote une fonction de 7 sur 2", ot F()) dénote ensemble des processus sujet de défaillances 4 instant # ; H; dénote historique d'un détecteur de défaillances, elle représente une fonction de TL * 7 sur 2!!, ot H(,0) est la valeur du module de détecteur de défaillance du processus palinstant ¢ T-; dénote le rang d’une horloge [Link]éte, et prend des valeurs naturelles. - La précision : Nous considérons les quatre propriétés de précision suivantes : Précision forte : aucun processus correct n’est suspecté. Formellement, D satisfait la précision forte si: VF,WH € D(F),WteT,Vp,q eT - F(t): pe Hq.) Précision faible : il existe au moins un processus correct qui n'est jamais suspecté. Formellement, D satisfait la précision faible si : VF,WH € D(F),3p € correct(F),Wt €T,q eT F(t): p H(q.t) Précision inéluctablement forte: il existe un instant ¢ partir duquel aucun processus correct n'est suspecté. Formellement, D_ satisfait la précision inéluctablement forte si : VFWH € D(F),3t€T,Vt2 1, ¥4p,q € correct(F): p€ H(q.) Précision inéluctablement faible : il existe un instant ¢ & partir duquel au moins un processus correct n’est jamais suspecté. Formellement, D_satisfait la précision inéluctablement faible si : WF,WH © D(F),3t € T,3p € correct(F), V2 1,4 € correct(F): p ¢ H(q.t') CHAPITRE 03 : Problémes d’accord 6.2 Classification : En combinant les deux propriétés de complétude et les quatre propriétés de précision, Chandra et Toueg [1996] définissent huit différentes classes de détecteurs de défaillances (Figure 3.2). Hors de ceux-ci, Chandra, Hadzilacos et Toueg ont montré dans [1996] que OW est Ia classe la plus faible de détecteurs de défaillance exigée pour résoudre le consensus. Ils ont aussi montré qu’un détecteur de défaillances de la classe OS et un autre de led, la classe OW sont équivalents, c.~d-d., l'un peut étre transformé & l’autre et vice versa. Précision Inéluctablement | Inéluctablement | Complétude Forte Faible Forte Faible | Parfait Fort Inéluctablement | Inéluctablement | Forte P S Parfait Fort | o | os | Faible Inéluctablement | Inéluctablement Faible | WwW Quasi-parfait Faible 00 ow Figure 2. L es classes de détecteurs de défaillances La transformation de la classe OS A OW est triviale, puisque OS est une sous-classe de OW. Pour transformer OW a OS, Chandra et Toueg ont proposé dans un algorithme distribué qui transforme la complétude faible une complétude forte, en préservant la précision. I en résulte done des équivalences entre les classes (P= O, S=W, 0P =00, 0S = OW). 10 CHAPITRE 03 : Problémes d’accord Cependant, un détecteur de défaillance est plus robuste s'il se base sur un algorithme plus simple, Par exemple, un algorithme qui résout le consensus est beaucoup plus simple si nous prenons un détecteur de défaillance de 1a classe OS que si on prend un détecteur de défaillances de la classe OW. clairement, le deuxiéme algorithme doit faire face au manque de complétude de OW en ce qui conceme OS. 7. Résolution du consensus en utilisant des détecteurs non fiables Chandra et Toueg [1996] ont proposé un algorithme de consensus basé sur un détecteur de défaillances de la classe 0S. La résolution du probléme du consensus gréce un détecteur de défaillances appartenant a cette classe ne sera réalisable que sous une condition essentielle. Ainsi, I’hypothese a laquelle le systéme doit répondre est que plus de la moitié des processus du systéme doivent étre corrects, c’est a dire qu’ils ne doivent subir aucune défaillance. me du coordonnateur rotatif, savoir Le principe de cet algorithme repose sur le paradi que Valgorithme se décompose en diverses rondes asynchrones chacune étant gérée par un processus différent, le procéssus coordonnateur de la ronde. Ce processus coordonufateur est le processus ¢ = (f mod N) + 1 oli r représente la ronde courante et N est le nombre de processus du systéme. Ainsi, & une ronde donnée, tous les messages en transit sont soit & destination du processus coordonnateur soit en sa provenance. Chaque ronde peut étre décomposée en 4 phases asynchrones. Durant la premiére phase, chaque processus du systéme envoie au coordonnateur son estimation de la valeur de décision affranchie avec le numéro de I'étape durant laquelle il a choisi cette estimation, La phase 2 consiste en la réception par le processus coordonnateur de (N +1)/2 messages envoyés durant la phase 1. Aprés avoir rassemblé ces diverses estimations, le processus coordonnateur séleetionne celle ayant le plus grand affranchissement et envoie cette nouvelle estimation a tous les processus du systéme. Chaque processus doit désormais recevoir cette nouvelle estimation. Cette réception ainsi que tés distinctes. Soit le son traitement représentent la troisiéme phase qui offre deux possi processus qui regoit cette nouvelle estimation envoie un acquittement au coordonnateur pour signifier qu’il adopte cette estimation. Soit aprés avoir consulté son module de détection de défaillances, le processus qui regoit cette nouvelle estimation (ou ne la regoit pas) suspecte la défaillance du coordonnateur, et envoie un "nack" & ce méme coordonnateur, Enfin, pour la quatriéme phase, le coordonnateur attend (N + 1)/2 réponses (“ack" ou "nack"). Si toutes les réponses sont des acquittements, alors le coordonnateur sait que la majorité des uw CHAPITRE 03 : Problémes d’accord processus a retenu cette nouvelle estimation, il envoie done a tous les processus la décision sur cette estimation. Sinon, si le coordonnateur a regu un "nack", il n’envoie pas de message de décision et passe directement 4 la ronde suivante. Une bonne caractéristique des algorithmes basés sur la classe OS est qu’ils sont sds, c-a-d., ils préservent la sfireté méme si ni la complétude forte ni la précision inéluctablement faible est satisfaite, en particulier, méme s‘il y a une défaillance qui n’est jamais détecté par aucun processus et que tous les processus correets sont & plusieurs repy s (et pour toujours) faussement suspectés. Phase 2 Phase 4 VALEUR - PROPOSI- SION Phase 1 Phase 3 Une ronde + —— Figure 3. Une ronde de Palgorithme de Chandra et Toueg 2

Vous aimerez peut-être aussi