LA TOLRANCE AUX PANNES

DANS LES SYSTMES RPARTIS

G. Florin

Laboratoire CEDRIC

CNAM

1
 PLAN DE L'EXPOSE

- Introduction: concepts de base de la sret

de fonctionnement

- Classification des pannes.

- Diffrents types de redondances.

- Principaux problmes de la tolrance aux

pannes.

- Conclusion.

2
INTRODUCTION: CONCEPTS DE BASE

DES SYSTMES REPARTIS

SURS DE FONCTIONNEMENT

3
 Systme sr ("dependable")

Qualitativement on peut avoir

"confiance" dans le service qu'il rend.

Systme rparti sr

- Ensemble de plusieurs calculateurs

relis en rseau qui collaborent pour des
traitements contrainte de sret

En contrle de processus industriel

. fortes contraintes de sret
. contraintes d'chances fortes/faibles
. support de dispositifs spcifiques

Mais aussi en gestion transactionnelle

. faibles contraintes de sret
. faibles contraintes d'chance

Tout systme rparti doit assurer la

prise en compte des contraintes de sret
(algorithmique rpartie des systmes et des
rseaux, calcul intensif, ...)

4
 Terminologie de la sret de
fonctionnement ("Dependability")

Les fautes (erreurs de conception,

accidents, malveillances)

L'existence d'erreurs de conception

("design errors") ou d'accidents physiques
("physical damage") ou de malveillances
est invitable.
- Erreurs de conception, programmation
ou de saisie.
- Accidents dus l'environnement.
- Malveillances intentionnelles.

Les tats errons

L'une des circonstances prcdentes
peut ne pas gner le systme ou le gner en
conduisant un tat erron (non prvu).
Cet tat peut rester indtect longtemps
(latence de la faute) mais conduit court ou
long terme une dfaillance ou panne.
Problme: dfinir la faute qui conduit
l'tat erron.

5
 Dfaillances, pannes
("Failures")

Le systme est en panne si suite l'un

des phnomnes prcdents il ne respecte
pas l'une de ses spcifications.

La panne est la manifestation au niveau

du service rendu d'une faute.

6
Systmes de scurit, systmes critiques
"Safety critical systems"

Le domaine d'utilisation du systme est

particulirement dangereux et met en jeu
des vies humaines avec des cots lis aux
pannes qui peuvent tre immenses.

Domaine des transports

- Conduite automatique de trains.
- Systmes de contrle en avionique.

Domaine de la production d'nergie

- Conduite de centrales nuclaires.
- Conduite de barrages.

Classification des pannes

- Pannes catastrophiques
Elles sont inacceptables

- Pannes non catastrophiques

Elles sont acceptables.
Notion de systme dfaillance saines
("Failsafe")

7
 Techniques pour la construction de
systmes srs

L'vitement des fautes

("Fault avoidance")
L'ensemble des techniques de conception,
de fabrication qui permettent de produire
des composants informatiques de trs bonne
qualit (trs fiable).

Le composant ne doit pas tomber en panne

- bonne conception
- bonne fabrication (gnie logiciel)
=> peu d'erreurs.

La tolrance aux fautes

("Fault tolerance")
L'ensemble des techniques de conception
des systmes qui continuent de fonctionner
mme en prsence de la panne de l'un de
leurs composants.
L'ensemble de l'architecture, considre
comme un tout, continue par l'utilisation de
redondances de rendre le service attendu en
dpit de l'existence de fautes.

8
 Techniques pour la validation de
systmes srs

L'limination des fautes

L'ensemble des techniques permettant

de minimiser le nombre de fautes
rsiduelles prsentes dans un systme (par
le test).

Techniques de validation, de tests

=> moins d'erreurs.

La prvision des fautes

("Fault measurement")
("Dependability evaluation")

L'ensemble des techniques de

l'valuation prvisionnelle de la sret de
fonctionnement (de l'existence de fautes).
L'ensemble de l'architecture considre
comme un tout continue par l'utilisation de
redondances de rendre le service attendu en
dpit de l'existence de fautes.

9
 Les composantes quantitatives de la
sret de fonctionnement

- La fiabilit ('Reliability') -
R(t) = Probabilit pour qu'un systme
soit continment en fonctionnement sur une
priode donne (entre 0 et t).

- La disponibilit ('availability') -
D(t) = Probabilit pour qu'un systme
soit en fonctionnement un instant t donn.

- La maintenabilit ('Maintainability) -
M(t)= Probabilit pour qu'un systme en
panne l'instant 0 soit rpar l'instant t.

- La scurit ('Security')-
S(t) = Probabilit pour qu'un systme
soit continment en fonctionnement non
catastrophique sur une priode donne
(entre 0 et t).

10
 Grandeurs moyennes caractristiques
de la sret de fonctionnement

- La disponibilit asymptotique -
La disponibilit aprs une longue dure:
D * = lim t + D (t )

- Le MTTF (Mean Time To Failure) -

Le temps moyen jusqu' la premire panne (si
R(t) est la fonction de fiabilit) :
+
MTTF = R(t )dt
0
- Le MUT (Mean Up Time) -
Le temps moyen de bon fonctionnement avant la
prochaine panne (en rgime stationnaire).

- Le MDT (Mean Down Time) -

Le temps moyen en panne avant la rparation
(en rgime stationnaire).

- Le MTBF (Mean Time Between Failure) -

Le temps moyen entre pannes (en rgime
stationnaire).
MTBF = MUT + MDT

11
 Sret de fonctionnement et systmes
rpartis

- La sret de fonctionnement d'un

systme rparti doit tre tudie.
Exemple: Architecture de n sites en
coopration : chaque site est indispensable
- Si le taux de panne d'un site est .
- Le taux de panne du systme est n.
- Hypothse exponentielle.
Notion de systme en srie: la fiabilit est
le produit des fiabilits:
R(t ) = Ri (t )
i

- Au contraire une organisation efficace

d'un systme rparti (en tolrance aux
pannes) atteint des niveaux de sret de
fonctionnement qu'aucune approche
d'vitement ne peut atteindre un cot
comparable.
Notion de systme en parallle:
R(t ) = 1 (1 Ri (t ))
i

12
 I

Classification des pannes

13
 Modle des systmes rpartis tudis

Un composant (matriel ou logiciel) est

considr comme correct s'il se comporte
de manire consistante avec ses
spcifications.

Un modle formel (ex: automate) dcrit

le comportement correct du composant.
Pour toute situation on connat :
. Un ensemble possible d'vnements
entrants.
. Les traitements raliser
. Les ensembles de messages produits en
rsultat
. Les contraintes de dlais de rponse
(dans de nombreux cas cette donne est
fondamentale).

Un composant en panne ne se comporte

pas selon ses spcifications de
comportement et de performances

14
 Consquences sur les quipements
matriels

Processeurs corrects
Excution du jeu d'instruction respect.
Respect de l'intgrit des donnes en
mmoire.
Temps de traitement conformes aux
spcifications.

Rseau de communication correct

- Topologie quelconque permettant tous
les changes ncessaires l'application.
- Dlai de transmission des messages
conformes aux spcifications.

Horloges physiques correctes

. Drive borne (par rapport un temps
universel utilis titre de comparaison)
Ex. : u, v dates universelles
c(u), c(v) valeurs lues
r drive maximum
(1 - r) (u - v) < c(u) - c(v) < (u - v ) (1 + r)

15
 Panne franche ("Crash")

Une fois le composant en panne franche

il cesse immdiatement et de faon
indfinie de rpondre toute sollicitation
ou de gnrer de nouvelles requtes (jusqu'
une rparation).
Une panne franche est une panne
permanente.

Ex. : .Panne franche de processeur.

. Coupure de voie physique.
. Certains types de programmes
errons (exemple boucle)
. Systme d'exploitation interbloqu.

Distinction

Systme silencieux sur panne

"Fail-silent"
En panne silencieuse le systme ne
produit plus aucune sortie.

Systme stopp sur panne

"Fail-stop"

16
 Modles de systmes relativement au
temps

Systmes synchrones

Ide de base
Deux systmes ne peuvent se mettre
agir des vitesses relatives non prvues.
. Les dlais de transmission des
messages sont borns (par une valeur D).
. Il existe une borne suprieure pour le
temps d'excution d'une tape par un
processus.
. Les horloges matrielles ont une
drive borne.
Hypothses temporelles synchrones
La rponse une sollicitation s'effectue
toujours dans un dlai born ou pas du tout.

Systmes asynchrones
On ne connat pas de borne au temps de
rponse une requte qui peut-tre
arbitraire.
Aucune hypothse temporelle n'est
formule.

17
 Dtecteurs des pannes franches.

Les hypothses synchrones permettent

l'utilisation de dlais de gardes pour la
construction de dtecteurs de pannes par
scrutation d'un processus.

Cas des systmes synchrones

Si le rseau ne perd pas de messages cette
solution dtecte les pannes franches.
Si le rseau est soumis des pertes de
messages cette solution est probabiliste.
Cas des systmes asynchrones
On ne peut pas distinguer le cas d'un
processus extrmement lent de celui d'une
panne franche.
Dlai de garde
P1
Cas synchrone
P2
P1
Cas asynchrone
P2
P1
Cas de panne franche
P2 synchrone ou asynchrone

18
 Proprits d'un dtecteur de pannes
franches.

Ide de la compltude ("Completeness")

Un processus en panne franche doit tre
dtect en panne.

Ide de la prcision ("Accuracy")

Un processus correct ne doit pas tre
considr en panne franche.

Raffinement des proprits des

dtecteurs de pannes franches
(Chandra et Toueg).

Compltude ("Completeness")

Compltude forte
Invitablement tout processus en panne
franche est suspect de manire permanente
par tout processus correct
Compltude faible
Invitablement tout processus en panne
franche est suspect de manire permanente
par un processus correct.

19
 Prcision ("Accuracy")

Prcision forte ("Strong Accuracy")

Aucun processus correct n'est suspect
avant de tomber en panne franche.

Prcision faible ("Weak Accuracy")

L'un des processus correct n'est jamais
suspect avant de tomber en panne franche.

Prcision forte invitable

("Eventual strong Accuracy")
Il existe une date au del de laquelle
aucun processus correct n'est suspect avant
de tomber en panne franche.

Prcision faible invitable

("Eventual weak Accuracy")
Il existe une date au del de laquelle l'un
des processus correct n'est jamais suspect
avant de tomber en panne franche.

20
 Catgories de dtecteurs de pannes
franches selon Chandra et Toueg

Combinaison des quatre niveaux de

prcision et des deux niveaux de
compltude.

Prcision
Invitablement Invitablement
Forte Faible Faible
Compltude Forte
Parfait Fort Invitablement Invitablement
Forte Parfait Fort
P S P S
Faible Invitablement
Faible Q W Q Faible
W

Avant Chandra et Toueg

Dfinition de problmes de sret de

fonctionnement rsolus sous hypothses
synchrones ou asynchrones.

Aprs Chandra et Toueg

Dfinition de problmes de sret de

fonctionnement rsolus sous hypothses de
fonctionnement des dtecteurs de pannes.
21
 Panne transitoire ou intermittente
"Transient, Intermittent,
Omission failure"
En rponse un vnement en entre un
composant ne dlivre jamais la rponse
attendue (le composant ne peut fournir son
service habituel pendant une certaine
priode => perte de quelques donnes).
Ultrieurement il peut fonctionner
nouveau de faon correcte.
Il n'y a pas dviation par rapport aux
spcifications sur ces autres rponses.
Distinction possible
Panne transitoire
Apparat une seule fois puis disparat.
Panne intermittente
Apparat plus ou moins priodiquement.
Exemples. :
. Perte de messages dues au bruit.
. Destruction de message pour viter la
congestion.
. Destruction d'activits pour viter
l'interblocage ou les problmes de contrle
de concurrence.

22
 Panne temporelle
"Timing, Performance failure"

. Une sortie correcte associe une

requte entrante se manifeste de faon
incohrente avec les spcifications
temporelles.

- Trop tard.

- Trop tt.

Le cas le plus frquent est celui d'une

manifestation trop tardive.

Ex. : . Surcharge d'un processeur.

. Horloge trop rapide.
. Dlai de transmission trop long.

Problme trait dans les cours de temps

rel (stratgies d'ordonnancements temps
rel) ou dans les cours de rseaux QOS
(respect de latence ou de gigue).

23
 Panne quelconque ou byzantine
("Malicious, byzantine Failures")

Tout comportement s'cartant des

spcifications (principalement en ce que les
rsultats sont non conformes) est qualifi de
comportement byzantin (Lamport).

On distingue quelquefois :

a) Fautes byzantines "naturelles"

Ex : . Erreur physique non dtecte (sur une
transmission de message, en mmoire, sur
une instruction).
. Erreur logicielle amenant une non
vrification des spcifications.

b) Fautes byzantines "malicieuses"

Ex : . Comportement visant faire chouer
le systme (sabotage, virus ....).

24
 Classification complmentaire des
pannes byzantines

- La signature des messages et la

vrification de signature (authentification et
intgrit) entrane une rsistance aux pannes
byzantines bien meilleure (surtout pour ce
qui concerne les modifications quelconques
qui pourraient tre effectues sur les
messages du fait de la transmission via des
sites malicieux).
- De manire plus gnrale l'usage des
fonctions cryptographiques simplifie les
protocoles de communication tolrant les
pannes byzantines.

On distingue donc parfois:

1) La classe des fautes byzantines

prcdemment dcrites (pour lesquelles les
communications sont non authentifies).

2) La classe des fautes byzantines qui

apparaissent malgr les signatures ("pannes
byzantines authentifies").

25
 Hirarchisation des classes de pannes

Les 4 classes sont hirarchises.

Panne franche:
Pas de rponse une entre
=> Panne transitoire

Panne transitoire:
Un dlai de rponse infini.
=> Panne temporelle

Panne temporelle:
Non respect d'une chance (spec)
=> Panne quelconque

Tolrance une classe de pannes

- On ralise des composants pour tolrer

l'une des classes de pannes prcdentes.
- Restent non tolres les pannes de la
classe suprieure.
- Cas les plus frquents:
Tolrance aux pannes franche
Tolrance aux pannes d'omission.

26
 II

Les diffrentes catgories

de redondance

27
 Rappel : Architectures redondances
matrielles

Exemple type : Architecture TANDEM

- Tolrance une panne franche matrielle

destine aux applications de gestion

- Systme orient disponibilit

CPU CPU

MEMOIRE MEMOIRE

Cont Disque Cont Disque

Cont Disque Cont Disque

Cont rseau Cont rseau

Voies physiques

28
 Les diffrents types de redondances

Nombreuses propositions
Nombreux points de vue

Techniques de recouvrement d'erreurs

("Error recovery")
1) Existence d'un dtecteur de panne.
2) D'un tat erron on peut retrouver un tat
correct puis dlivrer un service correct.

Reprises arrires
Redondances temporelles
("Backward Recovery")
- Pour un composant soumis des pannes
transitoires il est courant de tenter de
corriger cette panne par un nombre fix de
tentatives successives.
Ncessite la pose de points de reprise.

Z Cette technique est utilise assez

systmatiquement pour les serveurs uniques
et ce n'est qu'aprs l'chec de cette
approche que l'on dclare une panne non
temporaire.

29
 Reprises avants / Traitement
des exceptions / Poursuite
("Forward Recovery")

- Pour un composant soumis des pannes il

est courant de tenter de traiter cette panne
en recherchant un tat de cohrence du
systme n'ayant jamais exist (futur) ou
n'ayant pas exist dans un pass rcent (qui
s'apparenterait une reprise).

La reprise avant vite la pose de points de

reprise mais ncessite de dterminer
l'tendue des dommages causs aux systme
par la faute jusqu' la dtection de la
dfaillance.

Exemple : traitant/rcuprateur d'exception

30
 Techniques de compensation ou de
masquage d'erreurs

Un tat erron comporte des redondances

permettant au moyen d'un algorithme rapide
de dlivrer un service correct.

Redondances de donnes

- Pour une donne soumise des erreurs

(stockage, transmission) il est d'usage de
rajouter des informations de redondance
selon un code correcteur d'erreur qui
permet de corriger certaines erreurs.

31
 Redondances spatiales
ou redondances de groupes

- Un groupe de serveurs redondants g en

redondance spatiale est conu pour tolrer
la panne de certains de ses membres.

En dpit de la panne un certain niveau

de certains membres de g, le service offert
du point de vue global par g continue en
masquant le niveau de panne vis.

Par exemple on observe des pannes

quelconques si l'on masque les pannes
temporelles, transitoires et franches.
- ventuellement certaines performances
sont dgrades.
- Certains membres du groupe g clairement
dtects en panne sont isols et retirs du
groupe de serveurs redondants.
=> on reconfigure le groupe
=> jusqu' ce que la reconfiguration qui
maintienne un service acceptable devienne
impossible.

32
 Diffrentes redondances spatiales

Redondance passive
("Standby redundancy")
("Primary backup")
Objectif poursuivi : tolrance aux pannes
franches de calculateurs.
- Un seul des composants ralise
effectivement les traitements et est affect
aux sorties (le primaire).
- En cas de panne du primaire l'un des
calculateurs inactifs (secondaire) est
slectionn et activ pour prendre en charge
le service.
ACTIF
ENTREES PRIMAIRE

GESTIONNAIRE

DE LA
ENTREES INACTIF SORTIES

SECONDAIRE
REDONDANCE

(COMMUTATEUR)

ENTREES INACTIF

SECONDAIRE

33
 Problmes de synchronisation en
redondance passive

- Problme de dtection de panne du

primaire.
- Problme de dtermination d'un
nouveau primaire parmi les alternants.
- Pour le nouveau primaire il faut
reconstituer un contexte d'excution
correct.

Solutions possibles
. Recopie priodique d'informations de
reprise constitues par le primaire pour les
secondaires.
Priodes statiquement prdtermines
Points de reprise applicatifs.
. Rxcution des services fournis depuis le
dernier point de reprise.
Requte
Sauve

Fait
Rponse
Client Primaire Secondaire

34
 Redondances actives ou
dynamiques
("Active redundancy")

ACTIF

ENTREES SORTIES
ACTIF

GESTIONNAIRE
ACTIF
DE LA
REDONDANCE

- Dans la redondance active tous les

composants ralisent les traitements.

- Le gestionnaire de la redondance traite

les sorties pour tolrer diffrentes classes de
panne des serveurs.

35
 Redondance slective active

Tolrance des pannes franches

ACTIF (primaire)

ENTREES SORTIES

GESTIONNAIRE

ACTIF (secondaire) DE LA

REDONDANCE
COMMUTATEUR

- Un seul serveur est affect aux sorties

- En cas de panne du primaire le

secondaire prend le contrle (avec le
contexte d'excution complet de l'activit).

36
 Problmes de synchronisation en
redondance slective active

- Tout le monde doit recevoir les entres en

diffusion.

- Lors d'un basculement, l'alternant actif

doit tre rlu.

- Lors d'un basculement, le contexte de

l'alternant actif doit tre cohrent avec celui
laiss par l'ancien actif: besoin d'une
technique pour traiter dans le mme ordre
et exhaustivement les mmes donnes.
Diffusion ordonne totalement.

Remarque :
Le gestionnaire de la redondance peut-
tre plus complexe qu'un simple
commutateur. Quand les deux composants
sont actifs il peut choisir d'utiliser les
rsultats de l'un ou de l'autre selon les sites
de rsidence.

37
 Redondance massive
Tolrance des pannes quelconques.

ACTIF

ENTREES SORTIES
ACTIF

ACTIF
Voteur

TMR "Triple Modular Redundancy"

Entres Sorties

Capteurs Actionneurs

Etage Etage Etage Etage

de de de de
calculs votes calculs votes
Systme TMR avec rplication des voteurs

38
 Problmes de synchronisation en
redondance massive

- Tout le monde doit recevoir les entres en

diffusion dans le mme ordre pour traiter
les donnes dans le mme ordre et fournir
les rsultats dans le mme ordre aux
voteurs.

- La synchronisation entre les productions

de rsultats doit permettre la ralisation du
vote majoritaire.

Remarques:

Si l'on veut simplement tolrer des

pannes temporelles on peut prendre la
rponse disponible le plus rapidement.

Si l'on veut tolrer des pannes

quelconques on doit voter pour exclure
aussi bien les sorties non majoritaires que
celles qui apparaissent trop tardivement.

39
 Tolrance aux pannes logicielles

Si les calculateurs redondants ont la

mme panne le systme de redondance
massive ne fonctionne pas (de mme que les
solutions de reprise arrire).
Notion de panne de mode commun
Typiquement les pannes logicielles.
Solution: la diversification (fonctionnelle)
"N-Version programming"

- Diversification/isolement des quipes

Spcifications dtailles.
Dveloppement des codes.
- Diversification des processeurs
- Diversification des systmes.
- Diversification des compilateurs.
Variantes
- Dans le cadre des techniques de
redondances temporelles
("recovery blocks" Randell)
- Dans le cadre des techniques de
redondance massive.
Solutions coteuses et difficiles
raliser

40
 III

Les problmes fondamentaux des

systmes rpartis tolrants les pannes

41
 Rappel des diffrentes tapes d'un
mcanisme de tolrance (1)

Les principaux mcanismes de la

tolrance reposent sur l'existence de
services redondants dont les lments
peuvent tomber en panne.
a) Il faut tout d'abord dtecter les pannes
d'un ou plusieurs serveurs.
b) Si l'on peut formuler une hypothse de
panne transitoire et si les contraintes de
l'application sont compatibles avec les
techniques de recouvrement d'erreur (pas
trop temps rel fortement contraint) il faut
appliquer une technique de rxcution.
c) Si les redondances temporelles sont
insuffisantes il faut mettre en place des
redondances spatiales.
=> dcider de la suite des situations
d'appartenance au groupe de serveurs
redondants.
Les situations successives rsultent:
- des pannes des membres
- des rinsertions de composants ou des
adjonctions de serveurs nouveaux.

42
 Rappel des diffrentes tapes d'un
mcanisme de tolrance (2)

d) Il faut assurer des transmissions fiables

vers des groupes de composants redondants
(diffusion d'informations de chacun des
clients vers le groupe de serveurs
redondants implmentant un service).
Ces diffusions doivent tre ralises
sous les diffrentes hypothses de pannes et
satisfaire des proprits d'ordre.
e) Pour la redondance massive il faut
rechercher un consensus sur une valeur
calcule n fois (vote rparti).
f) Il faut ventuellement tolrer les
pannes temporelles (satisfaction de
contraintes temporelles pouvant tre
svres) => l'ordonnancement temps rel
rparti des tches.
Point essentiel pour la dtection des
pannes temporelles et pour la satisfaction
des contraintes temps rel rparti:
=> l'existence d'une synchronisation
des horloges entre les diffrents sites.

43
 Rappel des diffrentes tapes d'un
mcanisme de tolrance (3)

g) Si la programmation de l'application
organise des donnes rparties partages sur
diffrents sites il faut assurer le contrle de
l'accs concurrent aux donnes (maintien
de la cohrence) pour des donnes
dupliques.

h) Si la programmation de l'application
comporte encore des sites centraux
(redondances slectives) il faut prvoir la
dfaillance de ces serveurs.

D'ou une liste de problmes types

rsoudre pour une algorithmique
rpartie de la tolrance aux pannes

44
LA DTECTION DE COMPORTEMENT FAUTIF

Notion de composant autotestable:

un composant qui incorpore son propre
logiciel de diagnostic => qui fait passer le
plus vite possible un composant de l'tat de
faute latente l'tat de faute dtecte.
Existence de trs nombreuses techniques
Quelques exemples

- Utilisant des programmes de test

Dtection hors ligne (diagnostics).
Dtection en ligne (dtection continue).
Chien de garde=>surveillance mutuelle.
- Dtection des erreurs de donnes
Codes dtecteurs d'erreur.
Assertions/Tests d'acceptance.
Vote entre plusieurs alternants.
- Dtection des erreurs d'enchanement
Protection (anneaux, domaines).
Observation de points spcifiques de
l'excution => comparaison un rfrentiel.
Signature de squences
=> comparaison une tabulation des
squences valides.

45
 REPRISE ARRIERE

Problme classique de l'univers rparti.

Pour une application cooprative faisant

intervenir une architecture quelconque de
clients et de serveurs (ventuellement
redonds):
=> Comment dterminer des points de
reprise "cohrents" une frquence
optimale.

=> Comment assurer si ncessaire la

journalisation des messages en transit sur les
canaux de communications.

=> Comment effectuer la reprise arrire

en cas de panne dtecte.

Difficile pour obtenir des performances

satisfaisantes

46
PROTOCOLE D'APPARTENANCE A UN GROUPE

Objectif : Assurer que tous les usagers

ayant connatre la situation d'un groupe de
serveurs atteignent un consensus sur la
composition du groupe.

- La perception de cette composition est

relative des communications de
groupes (le protocole d'appartenance un
groupe est en gnral utilis conjointement
avec un protocole diffusion).

- Dans un tel protocole on admet souvent

que le temps est divis en poques ou la
composition du groupe est fixe et identique
pour tout le monde.

- A l'intrieur d'une mme poque les

communications en diffusion atteignent la
mme liste de processeurs ou chouent ce
qui peut advenir en priode de changement
de liste.

47
 LA DIFFUSION ET LE CONSENSUS

Objectif : Ces deux problmes

prcdents sont des variantes peu
diffrentes consistant faire s'accorder
diffrents composants d'un groupe sur une
valeur
- Valeur diffuse par un site.
- Valeur vote aprs un calcul en
redondance massive.

- La valeur est utilise comme un signal

pour dclencher un traitement (valeur
binaire)

Exemple du problme de validation dans

la mise jour des donnes ("commit")
- La valeur est utilise comme une
donne quelconque.
Exemple du problme de redondance
massive sur des donnes calcules comme
des valeurs envoyer sur des actionneurs.

48
 LE PROTOCOLE DE SYNCHRONISATION
D'HORLOGES

Objectif : Assurer que des horloges

situes sur des sites distincts fournissent une
datation absolue des vnements avec une
incertitude dfinie.

On distingue dans ce contexte deux

sous-problmes :

- Assurer que diffrents sites arrivent

dmarrer avec la mme heure absolue
(au mme moment avec une incertitude
connue).

- Maintenir aussi longtemps que

ncessaire les diffrentes horloges dans
une variation relative connue.
. En contrlant la drive relative

Solutions par change de messages.

Solutions par asservissement sur une
horloge hertzienne.

49
 LE PROTOCOLE D'LECTION

Objectif : Lorsqu'une solution un

problme est base sur l'existence d'un site
coordinateur unique la panne du
coordinateur doit tre tolre.

Cas des solutions en redondance

slective passive et slective active.

Le protocole d'lection vise dsigner

un et un seul coordinateur remplaant.

50
 CONCLUSION

Architecture de systmes rpartis en vue de

la tolrance aux pannes
Ncessit de fournir deux catgories de
services.

1 Les services standards utiliss dans des

systmes rpartis: micro-noyaux,
systmes d'objets rpartis
- Gestion des ressources (mmoire,
processeur/ordonnancement..)
- Dsignation, liaison
- Cration des objets, migration,
- Ralisation des interactions de base
(IPC, RPC lgers/distants)
- Synchronisation ... etc
La sret n'est pas leur objectif principal
La sret/tolrance aux pannes de ces
algorithmes est fondamentale car ils sont
utiliss dans un systme dont la sret doit
tre excellente.

51
2 Algorithmes utiliss dans les systmes
tolrants les pannes pour la tolrance.

Exemples vus:
Dtection de panne
Reprises arrire
lection
Diffusion fiable
Gestion des groupes
Vote rparti
Synchronisation d'horloges
Copies multiples
etc....

- La tolrance aux pannes des solutions

prsentes dans un systme rparti pour la
sret de fonctionnement est un problme
essentiel.

- Certains de ces algorithmes doivent tre

tudis pour tolrer tout type de panne.

52
 Bibliographie

1 R. Strong "Problems in fault-tolerant

distributed systems", Publication IEEE
ISBN 135-/85/0000/0300s01.00

2 F. Christian, "Issues in the design of

highly available computing systems",
IBM Research Report RJ 5856 (58907)
7/10/1987

3 F. Christian, "Questions to ask when

designing or attempting to understand a
fault-tolerant distributed system",
IBM Research Report RJ 6980 (66517)
4/8/1989

4 J.C. Laprie, B. Courtois, M.C. Gaudel ,

D. Powell "Sret de fonctionnement des
systmes informatiques matriels et
logiciels", AFCET Dunod Informatique
1989

53