PROBLEMES POSES PAR LES DEFAILLANCES
3.1-Résister aux fautes
Il est désormais classique de dire qu’une faute peut provoquer des erreurs qui peuvent entraîner des
défaillances. A leur tour ces défaillances peuvent entrainer des fautes, qui, etc.
Disons qu’un composant (ligne de communication ou site doté d’un texte d’algorithme à exécuter) est
défaillant lorsqu’il ne répond plus à sa spécification (fonctionnelle).
En ce qui concerne la communication et sa mise en œuvre, nous étudions ici les types de fautes les plus
communes, et après avoir présenté des outils aptes à y résister 4 problèmes particuliers seront passés en
revue.
Nous proposons quelques solutions assez générales à ces problèmes. Ce sont des solutions à même de
de faire face à de moult autre problèmes constitutifs de paradigmes nouveaux
3.1.1-Types de fautes
Les problèmes posés par la perte de messages sont passés en revue antérieurement (chapitre 2). Il
s’agissait des cas de contextes asynchrone et synchrone, et dans le cas où la ligne peut perdre les
messages mais n’est pas pour autant coupée (sectionnée). Il s’agit là, de la part des lignes, d’un
comportement défaillant dû à des fautes d’omission. La ligne transmet ou ne transmet pas les messages.
Il peut en être de même pour les sites : un site peut soit traiter le message reçu soit il ne fait rien. Il y a
alors ici omission.
C’est là précisément le premier type de faute que nous considérons : il est fondamental de voir qu’alors
si le composant fonctionne correctement.
Le second type de faute à considérer ici provient du comportement arbitraire des composants. On parle
alors de faute byzantine. Dans ce cas, le composant peut exhiber un comportement incorrect et cela à
l’insu des autres composants.
Dans l’exemple donné, soit un site S0 qui doit envoyer un même message à tous les autres sites (c’est
un broadcasting). En le faisant, il se trouve qu’il envoie un message m1 à certains sites et un autre m2
aux autres. Il s’agit clairement là, d’une faute byzantine. Résister à de telles fautes est très difficile (voire
impossible dans certains contextes). Les sites qui reçoivent les message de S0 peuvent alors se les
échanger pour vérifier si S0 présente ou non un comportement byzantin. Cependant, certains sites
pourraient être de mèche avec S0. Il y a alors collision entre sites. Ces derniers sites peuvent
communiquer comme valeur reçue de S0, des valeurs quelconques par exemple m3 et m1 ou pas de
message du tout. Le comportement byzantin est ici intentionnel. On parle même de comportement
malicieux. Il peut ne pas l’être dans le cas d’un canal qui altère le contenu d’un message et pour lequel
l’altération n’est pas détectée.
Il existe des classifications plus fines pour les différents types de fautes qui font apparaitre entre les
fautes d’omission et les fautes byzantines d’autres paliers.
3.1.2-Outils pour les solutions
Duplication : temporelle et spatiale
Résister aux fautes nécessite la duplication. Considérons pour illustrer ce propos, un canal qui peut
perdre les messages. Si le message m qui lui est confié est perdu, on doit le réémettre : il y a alors
duplication dans le temps. Si on place plusieurs canaux entre les 2 sites concernés, on peut envoyer le
message m sur chacun de ces canaux : il y a alors duplication dans l’espace.
La duplication constitue donc le premier outil pour résister aux défaillances.
1
Notion de protocole k-résistant
Quel que soit le type de duplication choisie, rien ne rassure que l’on puisse résister à la faute.
Considérons toujours l’exemple précédent : si l’on envoie le message k fois (duplication temporelle )
ou sur k lignes (duplication spatiale), il est possible que les k exemplaires du message se perdent. Il est
donc fondamental d’introduire la notion de protocole ou d’algorithme k-résistant. C’est-à-dire qui peut
résister à k fautes, éventuellement simultanées, k étant une valeur entière définie a priori. Le protocole
pouvant ne pas résister à davantage de fautes. Ainsi, dans l’exemple précédent k + 1 ré-émissions ou k
+ 1 lignes permettent de résister à k fautes s’omission.
Remarque
Il n’existe pas de protocole fini (qui termine de façon certaine en un temps fini) fondé simplement sur
les réémissions et les acquittements qui permette de transférer un message entre 2 sites via des lignes
qui peuvent perdre un nombre arbitraire de messages (problème de prise de décision commune, dans
l’exemple d’une armée en deux parties). Le caractère fini du protocole est ici obtenu en introduisant la
notion de protocole k résistant.
Détecter ou masquer
En considération, nous avons un canal qui peut altérer les messages qui lui sont confiés pour leur
transport et acheminement.
Si le même message est envoyé k + 1 fois ou sur k + 1 lignes différentes, le récepteur peut résister à k
altérations : s’il ne reçoit pas k + 1 messages identiques, il conclut que le message est altéré.
Il est possible dans ce cas d’aller plus loin en envoyant le message, 2k + 1 fois ou sur les 2k + 1 lignes.
Le récepteur considère la valeur majoritaire des 2k + 1 reçues, comme étant la valeur émise.
En d’autres termes, le (k + 1)-duplication permet de détecter, la (2k + 1)-duplication de masquer les
altérations de messages.
Implémenter : connexité et codes
Si les sites concernés ne sont pas voisins et si les sites intermédiaires fonctionnent correctement alors
les mêmes facteurs de duplication s’appliquent non plus sur les lignes mais sur les chemins indépendants
qui connectent les deux sites.
Un réseau est dit k-connexe s’il existe au moins k chemins indépendants entre tout couple de sites.
La k + 1 -connexité de les masquer s’il y en a au plus k.
L’association de codes aux messages (code de parité, code de redondance de type CRC, etc), est une
façon particulière d’implémenter la duplication.
Si à la réception le code n’indique pas d’altération le message est considéré correct. Dans le cas contraire,
si le code est détecteur on redemande la retransmission.
Si le code est correcteur on masque l’altération en le corrigeant. Ceci remplace les k + 1 ou 2k + 1
duplications mais requiert que les codes soient choisis avec soins : on suppose qu’ils permettent de
détecter / corriger toutes les altérations. Si ce n’est pas le cas, on doit associer à tout message que l’on
trouve non altéré une probabilité de l’être effectivement.
Délais de transfert
Certaines situations sont caractérisées par le fait qu’un site Si attend un message d’un autre site et que
ce message ne pourra jamais lui parvenir car : soit il s’est perdu, soit l’émetteur Sj ne l’enverra pas. Le
site Si ne pourra conclure en un temps fini que s’il connait le temps maximum β de transfert des
2
messages (ie : si le réseau est asynchrone) : il envoie une requête à Sj et attend 2β. Au terme de cette
attente, il pourra conclure. L’hypothèse d’un réseau synchrone est nécessaire pour résoudre de nombreux
problèmes.
Témoignages et signatures
Dans le cas où certains sites peuvent présenter un comportement byzantin, il importe comme déjà vu en
3.1.1 (S0 envoie m à tous les autres sites), que les sites doivent s’échanger les valeurs des messages
reçus de sorte à se mettre d’accord sur le message émis. Ainsi, chacun de ces sites témoigne aux autres
de la valeur reçue. Sj indique par exemple à Si ceci " S0 m’a envoyé m". Le problème réside dans le
fait qu’un site Si qui reçoit un tel message ne sait pas si Sj présente ou non un comportement byzantin.
Le témoignage reçu est-il correct ou falsifié ? Si pourrait être incapable de distinguer les 2 scenarios
suivants : (i) et (ii).
(i) scénario 1 : S0 est correct et a envoyé m0 à Si et à Sj. Si a reçu de Sj : " S0 m’a envoyé m1". (il
en résulte que Sj est byzantin)
(ii) scénario 2 : S0 est byzantin et a envoyé m0 à Si et m1 à Sj. Si a reçu de Sj : " S0 m’a envoyé m1".
(il en résulte que Sj est correct)
Une façon simple, pour permettre à Si de distinguer les 2 cas est d’utiliser des messages signés.
Tout message est signé par son émetteur. La signature de tout site Si est unique et ne peut être imitée.
Elle permet au destinataire de savoir si le message a été ou non modifié après avoir été signé.
Avec une telle technique (et il existe des systèmes de signatures à clé publique), il est possible de limiter
le témoignage d’un site byzantin en ce qui concerne la valeur reçue : soit à la retransmettre telle quelle,
soit à ne pas transmettre.
Dans le scénario 1, le site Sj qui a reçu m0 signé de S0, ne peut alors qu’envoyer " S0 m’a envoyé m0"
à Si ou ne rien faire (dans ce cas dernier, les délais bornés permettront à Si de conclure).
3.1.2-Problèmes possibles ou impossibles
Le problème de prise de décision (commune) était impossible sous certaines hypothèses vues en 1.6
(page 18).
Un autre problème est ici présenté et dont l’existence de solution dépend du contexte i.e. des hypothèses
faites.
Problème de la diffusion atomique
Soit un réseau (pour simplifier, on suppose un maillage complet : il existe une ligne entre tout couple de
sites) composé de n sites.
Les lignes sont fiables. Les sites peuvent fonctionner correctement i.e suivre les règles qu’on leur a
données, ou présenter des comportements byzantins.
Un des sites, soit S0, doit diffuser une valeur à tous les autres de sorte à ce que les propriétés suivantes
soient vérifiées à savoir (i) et (ii).
(i) : Propriété de sûreté :
- accord : tous les sites corrects se mettent d’accord sur une même valeur ;
-validité : Si S0 est correct alors la valeur d’accord est valeur émise par S0.
(ii) : Propriété de vivacité : l’accord entre les sites est obtenu en un temps fini.
Il s’agit d’un problème de diffusion dans un contexte où les sites peuvent présenter les pires
comportements possibles. Pour en comprendre la difficulté, il suffit de revenir aux deux scenarios décrits
précédemment.
3
C’est un problème d’importance capitale rencontrée par exemple dans la validation des transactions dans
un système réparti. Il est aussi rencontré dans le cadre de définition des entrées pour chaque processeur
d’un système utilisant la redondance. Toutes les sites participants doivent par exemple se mettre
d’accord sur le fait de valider ou d’invalider une transaction exécutée sur le site S0.
La diffusion atomique est un problème d’accord et une abstraction importante des calculs distribués
tolérants aux pannes. Elle assure que l’ensemble des messages échangés, par tous les processus du
système, soit délivré dans le même ordre. Ce travail présente un nouveau protocole de la diffusion
atomique dans un système à jeton utilisant les détecteurs de défaillances de la classe dans un cadre
synchrone.
Possible ou impossible
Le problème de la diffusion atomique n’a pas de solution dans un système asynchrone : on ne peut en
effet garantir la terminaison en un temps fini, un site byzantin pouvant faire défaut dans la transmission
des témoignages des valeurs reçues et le récepteur, ne pouvant distinguer le défaut de transmission d’un
temps de transfert de message infiniment lent, ne peut conclure à coup sûr en un temps fini.
Le problème a des solutions dans un contexte synchrone si certaines autres hypothèses sont satisfaites.
Considérons t le nombre maximum de sites dont le comportement peut être byzantin.
Le nombre minimum de phases d’échange, où les sites témoignent des valeurs reçues aux phases est
t + 1.
Si l’on n’utilise pas de messages signés, on doit de plus, avoir n ≥ 3t +1 avec (3t+1 = 2t+1 + t). Si les
messages sont signés, il suffit d’avoir n > t +1.
Dans le cas où le réseau n’est pas complet, celui-ci doit être (2t + 1) - connexe.
(Enfin, si on utilise le bus de diffusion à la place des lignes, le nombre de bus doit être supérieur à t et
le nombre de phases est ≥ 2).
Remarque ;
La diffusion atomique représente une classe des problèmes d'accord et une abstraction importante des
calculs distribués tolérants aux fautes. Elle assure que l'ensemble des messages, diffusés par les
différents processus, sera délivré par tous les processus de destination dans le même ordre.
Présentons une solution utilisant des messages signés.
Protocole déterministes ou probabiliste
Les protocoles ou algorithmes présentés jusqu’à présent étaient implicitement déterministes au sens où,
ils n’utilisent jamais de tirage de nombre aléatoire pour définir leur comportement : celui-ci ne dépend
que des valeurs initiales et des messages reçus.
Une manière d’essayer de donner des solutions aux problèmes qui n’ont pas de solutions déterministes
est de changer le modèle en considérant qu’un site peut déterminer son comportement en tirant des
nombres aléatoires. On parle alors d’algorithmes probabilistes.
Dans ce cas la propriété de la vivacité qui était "la terminaison est atteinte en x (valeur bornée) phases"
devient "la probabilité qu’un site n’ait pas terminé en y phases tend vers 0 lorsque y tend vers l’infini".
Le lecteur se reportera aux références "biblio" pour approfondissement de cette question.
Problème du consensus
Chaque site est initialement doté d’une valeur vi ∈ D ( D = {oui, non} par exemple). Nous cherchons à concevoir
un protocole qui puisse satisfaire les propriétés suivantes (i) et (ii) :
(i) : Propriété de sûreté :
4
-Accord : tous les sites se mettent d’accord sur une même valeur v ;
-validité : Si tous les sites corrects ont la même valeur initiale v alors la valeur d’accord est v.
(ii) : Propriété de vivacité : l’accord entre les sites est obtenu en un temps fini.
Une solution à ce problème (on voit l’utilité : tous les sites se mettent d’accord sur le résultat d’une
action commune) permet de résoudre le problème de diffusion atomique : S0 envoie sa valeur à tous les
autres sites ; La valeur est reçue par un site quelconque Si et alors sa valeur initiale dans le problème de
consensus.
Inversement, une solution au problème de la diffusion atomique permet de résoudre le problème de
consensus : chaque site, en parallèle avec les autres, utilise un protocole de diffusion atomique pour
transmettre sa valeur aux autres.
Au terme de ces exécutions, tous les sites ont alors obtenu le même ensemble de valeurs sur lequel, ils
peuvent appliquer une même fonction pour obtenir le même résultat (cette fonction doit satisfaire la
propriété de validité du problème de consensus. Ce qui est possible, puisque sur les n > 3t sites au moins
2t + 1 sont corrects). Les hypothèses sur l’existence des solutions sont évidemment les mêmes pour les
2 problèmes ; ceux-ci sont équivalents.
Quatre principaux cas d’étude (4 paradigmes) suivent. Les solutions peuvent être en tout ou en partie
exportées pour résoudre d’autres problèmes
3.2-Perte d’un jeton sur un anneau
3.2.1-Problème
A plusieurs reprises, l’on a montré l’intérêt que représente la structure de communication "séquentielle"
qu’est l’anneau unidirectionnel, exploitée par un jeton. Celle-ci peut collecter des informations, en
distribuer, assurer une exclusion mutuelle, etc.
Le problème qui se pose est celui de la perte du jeton si les canaux ne sont pas fiables ; On les suppose
toutefois FIFO : ils ne déséquencent pas les messages.
Supposons les n sites placés sur l’anneau dans l’ordre S0, S1, S2, S3, ..., S1, Sn-1, S0,
Si le jeton se perd par exemple entre Si et SI+1 deux choses sont à faire :
(i) : détecter la perte du jeton ;
(ii) : en générer un nouvel exemplaire.
Si le jeton se perd et que plusieurs sites le détectent il est essentiel qu’un et un seul d’entre eux le
régénère ; Il se pose donc le problème d’exclusion (que le jeton avait peut-être pour but de résoudre).
En d’autres termes, le jeton n’est pas un simple message qui transite entre 2 sites, il s’agit d’un message
dont la portée est l’ensemble des sites. Deux types de solutions sont à présenter pour résister à la perte
d’un tel message. Ce sont "valuer le jeton" et "utiliser un autre jeton".
3.2.2-Valuer le jeton
Principe
Un simple mécanisme d’acquittement du jeton entre 2 sites voisins est insuffisant pour résister à la
perte : la perte de l’acquittement peut en effet entrainer la présence de plusieurs jetons sur l’anneau. Une
solution simple consiste à valuer le jeton. Cette valeur obtenue est à utiliser pour laisser sur chaque site
une trace qui donnera les informations nécessaires pour détecter la perte éventuelle du jeton et le
régénérer si tel est le cas avec la bonne valeur.
Deux valuations simples sont possibles :
-le jeton peut compter le nombre de sites visités ou
-le nombre de tours effectués sur l’anneau.
Examinons la seconde valuation (et le premier à titre d’exercice) .
5
Comme l’on désire compter le nombre de tours, il est nécessaire de choisir un site comme début du tour.
Soit S0, ce site. Il aura pour charge d’incrémenter la valeur vj associée au jeton chaque fois qu’il le verra
passer.
Appelons $i la variable d’état locale au site Si , dans laquelle celui-ci place la valeur de vj du jeton
lorsqu’il le possède et cela avant de le transmettre à Si + 1 :
Var entier croissant init 0 : $i ;
Lorsque Si passe le jeton à Si + 1 , il arme une horloge de garde locale hgi à une valeur ∆. Lorsque ce délai
est écoulé le site Si va chercher à savoir si le jeton s’est perdu entre son prédécesseur Si - 1 et lui-même.
Tout site est donc chargé de détecter la perte entre son prédécesseur et lui-même. Ce qui règle le
problème d’exclusion mutuelle précédent : si le jeton est perdu un seul site le détectera et donc le
régénérera. Il s’agit donc de trouver un test qui indique la perte du jeton entre Si - 1 et Si.
Considérons à un instant, la configuration suivante des variables d’état :
( $0 = x, $1 = x, ..., $i - 1 = x, $i = x - 1, ..., $n - 1 = x – 1)
Le jeton a fait n-1 tours et le nième tour jusqu’à Si-1 qui l’a envoyé à Si. Si le jeton n’est pas perdu entre
Si-1 et Si (i ≠ 0), on a donc $i - 1 ≠ $i.
Le protocole est simple : à l’échéance de son horloge de garde, le site Si demande à son voisin de gauche
(prédécesseur) la valeur de sa variable d’état ($i – 1). Si celle-ci est égale à $i, le site Si conclut que le
jeton n’est pas perdu entre son prédécesseur et lui-même. Dans l cas contraire, il conclut à la perte et le
régénère avec la valeur obtenue de son voisin (figure ...). (le schéma demande-réponse utilise les
solutions classiques vues au chapitre 1.4 permettant une communication fiable entre deux sites).
L’anneau présente un point singulier S0 : le début du tour. Si le jeton est en transit ou se perd entre Sn-1
et S0, toutes les variables d’état sont égales. Le test détection est donc pour S0 l’égalité de $0 avec la
valeur de $n-1.
xi ≠ v
$i
demande
v
x
jeton
$i - 1
xi-1 = v
Figure 1: Détection de la perte
Protocole
De manière générale, on peut supposer que les sites peuvent tomber en panne et qu’alors un protocole
sous-jacent reconfigure l’anneau. Tout site est alors doté de deux variables vgi et vdi qui définissent
respectivement son voisin de gauche et son voisin de droite. Ce protocole garantit que les sites sont
toujours placés dans l’ordre de leurs identité sur l’anneau.
Dans le cas où S0 est défaillant, c’est S1 qui marquera alors le début du tour de l’anneau, etc.
De manière générale, le site de début du tour, et qui doit donc incrémenter vj, est le site tel que i < vgi.
Grâce au placement ordonné des sites sur l’anneau, ce site est unique.
Le protocole de détection et régénération est finalement le suivant pour un site quelconque :
visite du jeton
attendre jeton(vj) de Svgi ;
désarmer hgi ;
6
< utiliser le jeton conformément aux droits qu’il offre > ;
si i < vgi alors %début d’un nouveau tour%
vj := vj + 1
fsin
$i= vj ;
envoyer jeton(vj) à Svdi ;
armer (hgi , ∆)
lors de l’échéance ou Si a besoin du jeton et ne l’a pas
début
demander l valeur de Svgi à Svdi ;
% Svgi ne répond que s’il n’a pas le jeton %
si (i < vgi et $i=$vgi) % Si début du tour %
ou ( i > vgi et $i ≠ $vgi ) % Si banalisé %
alors % jeton($vgi) s’est perdu entre les 2 sites %
créer un jeton ($vgi)
% Si a alos le jeton %
fsi
on constate que d’une part, le seul test sur les valeurs du jeton ou les traces sont l’égalité et la différence
et que d’autre part la seule opération est une incrémentation de 1. La valeur du jeton et les variables $i
peuvent donc être implémentées modulo 2 : un bit suffit. Ceci est à rapprocher du protocole du bit alterné (chapitre
1/ 1.4.3.2) dans lequel les canaux sont également supposés FIFO. Si les canaux ne sont pas FIFO, cet algorithme
peut être adapté : les tests sont alors > ou ≤ à la place des précédents, et il n’est plus possible d’avoir des variables
bornées.
Il est important de constater que dans tous les cas, les valeurs de ∆. Utilisées peuvent être quelconques,
différentes pour plusieurs sites et d’un tour à l’autre. Les fondements de ce protocole sont, outre
l’utilisation de traces laissées par le jeton, l’existence d’horloge de garde (qui oblige le site à se poser la
question : le jeton est-il perdu entre mon voisin et moi) et le placement ordonné des sites sur l’anneau
(qui permet de définir des tests cohérents en définissant un site du début tour sur l’anneau).
3.2.3- Utiliser un autre jeton
Principe
Afin d’éliminer les horloges de garde et le placement ordonné des sites sur l’anneau, une idée simple
consiste à introduire plusieurs jetons dont chacun est chargé de détecter la perte éventuelle des autres :
tant qu’il y a un jeton, le système peut donc fonctionner.
Une étude probabiliste peut indiquer le nombre de jetons à utiliser, en fonction des caractéristiques des
canaux, pour que la probabilité qu’il y ait toujours au moins un jeton soit proche de un que l’on veut.
On se limite dans ce qui suit à 2 jetons.
Un jeton arrivé sur un site Si peut garantir que l’autre s’est perdu si, les canaux étant fifo, depuis son
passage précédent sur ce site, ni le jeton, ni Si n’ont rencontré l’autre jeton.
Protocole
Soit ping et pong les deux jetons. Ils sont valués respectivement par nbi et nbo qui comptent le nombre
de fois où ils se sont rencontrés et sont tels que nbi + nbo = 0.
Leurs valeurs initiales sont respectivement 1 et -1.
Chaque site est doté de d’une variable mi dans laquelle le jeton dépose sa valeur (trace) lorsqu’il est sur
ce site.
7
Lorsqu’un jeton, par exemple ping (nbi), arrive sur Si, si mi ≠ nbi, le jeton ou le site ont vu l’autre jeton
depuis le précédent passage de ping sur Si. Dans le cas contraire le site Si peut conclure à la perte d pong et
le régénérer.
Ainsi constaté, ni les identités des sites, ni des horloges de garde sont des nécessaires.
Le comportement d’un site Si quelconque peut alors être décrit par :
Lors de la réception de ping (nbi)
si mi ≠ nbi alors mi : = nbi
sinon % regénérer pong(nbo) %
nbi : = nbi +1 ;
nbo := -nbo ;
fsi
Lors de la réception de pong (nbo)
<text qui suit est analogue au cas précédent en intervertissant les deux jetons>
si mi ≠ nbo alors mi : = nbo
sinon % regénérer ping(nbi) %
nbo : = nbo +1 ;
nbi := -nbi ;
fsi
Lors de la réception des deux jetons (sur un site)
Début
nbi : = nbi +1 ;
nbo := nbo – 1 ;
fsi
Ce protocole revient à maintenir invariante la relation donnée par : nbi + nbo = 0.
Les variables manipulées peuvent être bornées. En effet les 2 jetons se rencontrent au plus une fois par
site et par tour d’anneau, soit au plus n fois par tour d’anneau. Les variables mi des sites ne peuvent donc
prendre au plus n valeurs différentes (en valeurs absolues). Les compteurs nbi et nbo peuvent donc être
utilisées modulo n+1 : entre deux visites à n’a pu être incrémenté que de n au plus (en valeur absolue).
D’autres mises en œuvre de ce même principe sont possibles. Dans la précédente, un tour de jeton est
nécessaire pour détecter la perte de l’autre. On peut vouloir la détecter " au plus tôt " : si pong s’est
perdu entre Si et son successeur sur l’anneau Sj alors ping détecte la perte en Sj et non pas après un tour
supplémentaire d’anneau. Pour réaliser cela, les jetons doivent être valués non avec le nombre de leurs
rencontres, mais avec le nombre de sites visités qu’ils, laissent en trace dans ces sites. Ainsi, ping peut
constater que pong est passé en Si, qu’il ne l’a pas rencontré et qu’il n’est pas arrivé en Sj. . Ecrire le
protocole correspondant à titre d’exercice.
3.3 Diffusion atomique
3.3.1-Problème
Le problème n’a jusque-là eu de solution que dans un cadre synchrone. C’est une hypothèse pour
garantir la propriété de vivacité. Un site qui attend un message ne doit pas l’attendre indéfiniment si
l’émetteur potentiel ne l’a pas émis.
Nous étudions deux solutions à ce type de problèmes. Dans la première, on considère que les seules
entraves au fonctionnement sont l’arrêt des sites (crash faults), et dans la seconde les comportements
byzantins sont possibles.
8
3.3.2-Sites à arrêt sur fautes
On suppose ici qu’un site peut s’arrêter de fonctionner mais ne peut en aucun cas se comporter de
façon byzantine. L’hypothèse de synchronisme s’exprime ici de façon suivante : les défaillances sont
détectées i.e (c’est-à-dire) l’arrêt d’un site est connu des autres au bout d’un temps fini. Ceci peut
facilement être mis en œuvre par un protocole de suspicion mutuelle avec des délais bornées (un site
ne peut alors confondre un message lent et émetteur arrêté.
Le réseau est supposé fiable. Afin de résister à t sites défaillants, qui alors ne relaient plus les
messages, le réseau doit être t + 1-connexe (il y a t + 1 chemins indépendants entre tout couple de
sites (rappelé)).
Lorsque le site S0 veut diffuser un message, il l’envoie à tous ses voisins qui le relaient vers leurs
propres voisins, etc ainsi de suite. Si stoppe après avoir envoyé le message à certains voisins mais pas
à tous, les sites non défaillants qui ont une copie du message pourront jouer (à leur tour) le rôle de S0
lors qu’ils apprendront qu’il ‘ce dernier) est défaillant. Si aucun d’eux ne reçoit le message la diffusion
est terminée.
Dans le cas où S0 désire diffuser une séquence de message, il doit leur associer un numéro de séquence
et des acquittements doivent être utilisés afin que tous les sites corrects reçoivent les messages dans le
même ordre.
La gestion du renvoi des acquittements s’appuie sur la connaissance des sites défaillants pour ne pas
attendre indéfiniment un acquittement qui ne sera jamais émis. Lorsque le message de numéro x a été
acquitté, le suivant peut être émis, ce qui garantit un ordre de réception unique.
3.3.3- Sites au comportement byzantin
Hypothèses
Dans ce contexte, un site peut envoyer des messages différents pour témoigner d’un même message
diffusé.
Supposons un réseau complet, des canaux fiables. De plus, nous allons utiliser des messages signés : un
site qui relaie un message ne peut donc l’altérer.
Avec l’utilisation de signatures, un site au comportement byzantin ne peut donc qu’ "oublier" de faire
suivre un message lors d’une phase d’échanges. La différence essentielle avec l’arrêt sur fautes est qu’ici
il ne les "oublie" pas tous et les autres ne savent pas qu’il est fautif.
Les messages signés sont représentés de la façon suivante : (ij représente l’identité du site et sa
signature :
v : i1, i2, ……, ik
i1 a envoyé la valeur v avec sa signature à i2 qui a signé ce message et l’a envoyé à i3 qui l’a signé etc.
sa signification est la suivante : à la kième phase d’échange Si reçoit ce message qui lui dit : " à la phase
k-1 le site Sik a reçu un message qui lui indiquait qu’à la phase k-2 le site Sik-2 a reçu un message qui
... qu’à la phase 1 le site Si1 lui a envoyé v". Un tel message est dit valide pour Si à la phase k s’il a
la forme précédente (k signature toutes différentes) et s’il ne contient pas la signature de Si.
La phase 1 commence à l’instant α, connu de tous, δ et ε représentant le délai de transfert maximum et
l’écart maximal entre 2 horloges, la phase k démarre à l’heure locale α + k δ + ε pour chaque site (on
suppose les temps de traitement nuls ou intégrés dans la borne δ ).
Protocole
Chaque site Si est doté de 2 variables : vali et reçui. il s’agit de 2 ensembles initialement vides vali va
contenir les valeurs émises par le site diffuseur S0 (si S0 est correct il n’y aura à la fin qu’une seule
valeur) et reçui sert à mémoriser les messages reçus par Si à la phase courante et qui sont valides. On ne
9
décrit bien sûr que le comportement des sites corrects (si S0 ou un autre n’est pas correct il n’existe pas
le texte indiqué).
Phase 1
1-S0 envoie : 0 à tous les autres
2-∀ i : 1 ≤ i ≤ n-1 (les autres)
recui := {messages valides reçus par Si} ;
vali := {valeurs contenues dans les messages de reçui}
Phase k : 2 ≤ k ≤ t+1, ∀ i : 1 ≤ i ≤ n -1
1- ∀ m ∈ recui : Si signe m et le diffuse aux autres ;
% il y a alors k signatures dans m %
2- recui := { messages valides reçus par Si à cette phase}
3- vali := vali ∪ {valeurs contenues dans les messages de reçui }
Fin de la phase t+1, 2 ∀ i 1 ≤ i ≤ n-1
si card (vali) = 1 alors valeur d’accord = valeur dans vali
sinon valeur d’accord = valeur par défaut prédéfinie
fsi
Les messages reçus qui ne sont pas valides (tentatives d’altérations, signatures imitées, nombre de
signatures incorrect) sont ignorés.
Preuve (informelle)
La terminaison est évidence : elle se produit à la fin de la phase t+1. Il s’agit de montrer l’accord et la
validité de cet accord. Pour cela, nous considérons les 2 cas selon que S0 est non ouvert.
Si S0 est ouvert, il envoie effectivement une et une seule valeur signée à tous les autres v : 0. Les sites
corrects placent alors v dans leur ensemble vali. Puisque aucun autre site ne peut falsifier le message
v : 0 (à cause des signatures) et que tout message doit contenir k signatures différentes à la place k,
aucun message valide ne peut contenir une autre valeur que v.
On a donc vali = { v } pour tous les sites corrects à la terminaison, c’est-à-dire un accord valide.
Supposons maintenant que S0 ait un comportement byzantin : il peut envoyer à la phase 1 des valeurs
distinctes aux autres sites, voire pas de valeurs à certains. Nous allons montrer qu’à la fin l’on a
vali = valj pour tout coule de sites corrects (d’où l’on conclut qu’il y a accord et qu’il est valide). Si v ∈
vali , appelons m le premier message placé par Si dans reçui qui transportait la valeur v. Deux cas se
présentent selon la phase à laquelle m est arrivé. Si m est arrivé avant ou au plus tard à la phase t, Si l’a
retransmis, après lui avoir ajouté sa signature, vers Sj à la phase suivante. Celui-ci l’a alors placé dans
recuj et a ajouté v à valj. Si par contre est arrivé à la phase t+1, par construction de l’algorithme, il
transporte t+1 signatures différentes, or il y a au plus t sites qui peuvent présenter un comportement
incorrect. On en conclut qu’au moins un site correct a reçu la valeur v lors d’une phase k < t+1 et l’a
dons retransmis à tous les autres sites corrects. On a donc dans tous les cas vali = valj.
Remarque 1
De card (vali) ≠ 1, le site Si peut conclure au fait que S0 présente un comportement byzantin. Par contre,
il ne peut rien conclure à ce sujet de card(vali) =1. En effet, cela indique que S0 n’a émis qu’une valeur
v mais il a pu envoyer v à certains sites et rien à d’autres.
Remarque 2
Cet algorithme requiert un nombre de messages qui dans le pire des cas est 0(n t). on peut facilement
ramener ce nombre à 0(n2) en constatant que dès que card (vali) ≥ 2, un site sait que S0 est incorrect.
10
Pour "en avertir " les autres, il suffit de relayer seulement les 2 premiers messages qui véhiculent des
valeurs et de rien transmettre ensuite.
3.4- Diffusion ordonnée atomique
Diffusion ordonnée : il existe un certain nombre de problèmes qui nécessite pour leur résolution une
primitive de diffusion dans laquelle tous les sites doivent recevoir les messages émis. Ceci n’est
généralement pas suffisant. Il faut de plus que, si plusieurs messages sont diffusés, ceux-ci soient reçus
dans le même ordre. On parle alors de diffusion ordonnée. Il en existe de types différents dont ces
trois : diffusion ordonnée à source unique ou simple (un seul émetteur), diffusion ordonnée à source
multiple et diffusion ordonnée générale (p130).
Dans le cas où les sites peuvent être défaillants, la terminaison (vivacité) peut être obtenue grâce à un
réseau synchrone.
La propriété de sûreté (même ordre de réception chez tous les sites corrects) peut être obtenue en
estampillant les messages avec leurs dates physiques d’émission comme (6.3.3 p137).
Si l’on veut résister aux comportements byzantins une solution simple est d’utiliser des messages signés
(comme précédemment).
Considérons un réseau quelconque dans lequel p sites et c canaux au plus peuvent être défaillants. On
suppose que, quels que soient les sites et canaux défaillants, le réseau résultant reste connexe et on
appelle d(p, c), le diamètre de ce réseau résultant.
L’algorithme 6.3.3 est alors correct en prenant maintenant comme valeur Δ =p(δ + ε) + d(p, c)δ+ ε.
La première quantité p(δ + ε) exprime le temps maximum nécessaire à un message pour atteindre un site
correct (s’il en existe un). La seconde quantité d(p, c)δ+ ε exprime le temps maximum pour atteindre
tous les sites depuis un site correct.
11
