Cours de Syst mes R partis:
Partie 1: Algorithmique R partie
Promotion BADS
AU 2019/20
Plan
Introduction
Bases de lalgorithmique r partie
1. Etat dans un syst me r parti, ordre, temps,
2. Observation coh rente
3. Algorithmique r partie
2
D finition dun syst me r parti
Ensemble compos d l ments reli s par
les
un syst me de communication
l ments ont des fonctions de traitement
(processeurs), de stockage (m moire), de
relation avec le monde ext rieur (capteurs,
actionneurs)
;
3
Propri t s des syst mes r partis
Fonctionner (au moins de fa on d grad e) m me en cas de
d faillance de certains de ses l ments
R sister des perturbations du syst me de communication
(perte de messages, d connexion temporaire, performances
d grad es)
R sister des attaques contre sa s curit (tentatives de
violation de la confidentialit et de lint grit , usage indu de
ressources, d ni de service)
Sadapter pour faire face aux changements de conditions
dutilisation et denvironnement
Rester performant lorsque sa taille augmente (nombre
d l ments, nombre dutilisateurs, tendue g ographique)
4
Difficult s dans les syst mes
r partis
Propri t dasynchronisme du syst me de communication (pas de borne
sup rieure stricte pour le temps de transmission dun message)
Cons quence : difficult pour d tecter les d faillances
Dynamisme (la composition du syst me change en permanence)
Cons quences : difficult pour d finir un tat global
Difficult pour administrer le syst me
Taille complexe et d velopp e (nombre de composants, dutilisateurs,
dispersion g ographique)
Cons quence : la capacit de croissance est une propri t importante,
mais difficile r aliser
En d pit de ces difficult s, des syst mes r partis existent tels
que:
le DNS (Domain Name System)
le World Wide Web
divers services sur lInternet
(service de base)
(infrastructure)
(applications)
5
Probl mes fondamentaux
Comment d terminer des propri t s globales partir
dobservations locales ?
Comment coordonner des op rations en
labsence
dhorloge commune ?
Comment d finir, et maintenir, la coh rence dinformations
r parties ?
Comment garder un syst me en fonctionnement malgr
des d faillances partielles
6
Solutions fondamentales
Il faut d finir des mod les
Un mod le est une repr sentation du monde r el
Un mod le repr sente des l ments r els par des l ments abstraits
Un m me syst me r el peut tre repr sent par des mod les
diff rents
Tout mod le a des limites
Il faut utiliser les mod les
Pour observer et comprendre le comportement du syst me r el
Pour pr dire le comportement du syst me r el dans certaines
circonstances
Pour aider commander le syst me r el (lui imposer un
comportement particulier)
7
Bases de lalgorithmique r partie
1. Ordre, temps, tat dans un syst me
r parti
2. Observation coh rente
3. Algorithmes r partis de base
8
Ordre, temps, tat dans un syst me
r parti
On veut tre capable de raisonner sur un syst me ou une
application
D finir des pr dicats, ce qui implique dacc der un tat
Coordonner des activit s, ce qui implique de d finir un ordre
Univers r parti est diff rent:
Pas de m moire commune (support habituel de l tat)
Pas dhorloge commune (qui d finit le s quencement des
v nements)
Asynchronisme des communications
Pas de borne sup rieure sur le temps de transit dun message
Asynchronisme des traitements
Pas de bornes sur le rapport relatif des vitesses dex cution sur deux
sites
Cons quence de la variabilit de la charge et de labsence (en g n ral)
de garanties sur lallocation des ressources
9
S ret et vivacit
On est souvent amen sp cifier et v rifier
des propri t s dun syst me dynamique
( voluant dans le temps)
Ces propri t s ont deux valeurs:
S ret (safety) : un v nement ind sirable
narrivera jamais
Exemples : violation de lexclusion mutuelle incoh rence
dans les donn es
Vivacit (liveness) : un v nement d sirable
finira par arriver
Exemples : un message sera d livr son destinataire
une ressource demand e sera rendue disponible
un algorithme se termine
10
Le mod le asynchrone (fiable)
Le but est de mod liser certains
aspects du monde r el
Asynchronisme des communications et des
traitements
Cest le mod le le plus faible
Les contraintes sont les plus fortes les
r sultats sont les plus g n raux
Bornes sur les co ts
R sultats dimpossibilit
" Le mod le peut tre renforc (en levant
certaines contraintes
Exemple : borne sup rieure sur le traitement
et/ou la dur e de transmission
11
Le mod le asynchrone
Les processus (sur diff rents sites) ne
communiquent que par messages
Trois types d v nements
Local (changement de l tat dun processus)
Li la communication
mission dun message
R ception dun message
Pas de bornes sur :
"la dur e de
transmission dun
message
"le rapport des vitesses
dex cution des
processus
12
R ception / D livrance
On suppose disponible un syst me de communication
permettant denvoyer des messages entre processus
Propri t s :
1. Un message finit par arriver destination, mais son temps
de transmission nest pas born !; on mod lise ainsi une
panne (d tect e) suivie dune ou plusieurs r mission(s)
2. Un message arrive intact (non modifi ) ; on suppose que
des m canismes de d tection / correction derreur sont
utilis s
3. Selon le cas, on fera ou non lhypoth se que le canal est
FIFO entre deux processus
13
Advertisement
R ception / D livrance
Bien distinguer la r ception dun
message de sa d livrance son
destinataire
14
v nements, historique, synchronisation
Lex cution dun processus est une suite
d v nements (local, mission, r ception) appel e
historique (ou trace) du processus
pour p1 : e11, e12, e13, &, e1k, &
Cette suite est ordonn e par lhorloge locale du
processus p1
Que veut dire synchroniser deux processus ?
Imposer un ordre entre des v nements
appartenant ces deux processus
Exemple : lexclusion mutuelle
fin(C2) pr c de deb(C1) ou fin(C1) pr c de deb(C2)
15
Relation de pr c dence
Le probl me :
1) D finir une relation globale de pr c dence (donner un
sens lop rateur pr c de )
2) D finir un ordre entre deux v nements sur la seule
base dinformations locales
Solution : utiliser le principe de causalit : la cause
pr c de leffet. Une relation de pr c dence est dite
causale si elle est compatible avec ce principe.
Application ici :
Sur un processus : un v nement local ne peut agir
localement que sur les v nements post rieurs
Entre deux processus : lenvoi dun message pr c de sa
r ception
Composition : la relation de causalit est transitive
16
La causalit
D finition :
e pr c de causalement e' ( e e') si :
17
La causalit est potentielle
La relation de pr c dence causale ! d finit en
fait une causalit potentielle (par n gation)
Si e e', on peut simplement dire quon ne
viole pas le principe de causalit en disant que e
est la cause de e'. On peut donc dire que e est
une cause potentielle de e', mais pas que e est
effectivement une cause de e' (il faudrait pour
cela analyser la s mantique de lapplication)
Certitude que e' ne peut pas tre la cause de e
(le futur nagit pas sur le pass )
18
D pendance et ind pendance
causale
D finition : pass (ou historique) dun v nement e
hist(e) = lensemble des e' tels que e' e {e}
Seul le pass strict de e peut influencer e
si e' e, alors e' peut influencer e
si (e e), alors il est certain que e' ne peut pas
influencer e
Si (e e') et (e' e), on note e || e' et on dit
que e et e' sont causalement ind pendants (aucun
des deux nappartient au pass de lautre, aucun
des deux ne peut influencer lautre)
19
Probl me de datation
Probl me : construire un syst me de datation
des v nements compatible avec la causalit
Approche : introduire un processus
observateur p0 qui est inform , par message,
de tout v nement du syst me
La suite des v nements enregistr e par p0
est une observation globale du syst me
20
Probl me de datation
21
Probl me de datation: Validit
des observations
Une observation du syst me est un
ordonnancement particulier des v nements
du syst me.
Une observation est dite valide si pour tout
couple d v nements (e, e') tels que
e e', O(e) pr c de O(e'). Sinon, elle est dite invalide (elle
viole la causalit )
22
Probl me de datation: Validit
des observations
Canal non FIFO. Lobservation viole la
causalit : les v nements sont observ s
dans lordre inverse de leur occurrence
23
Probl me de datation: Validit
des observations
La causalit est encore viol e :
e1
1 e2
lordre inverse.
2 , mais ces v nements sont observ s dans
Ce ph nom ne est ind pendant de la propri t
FIFO
24
Observation valide
Temporairement, lever lhypoth se
dasynchronisme
temps de transmission born = & et supposer quon
dispose dune horloge HR donnant le temps r el.
Chaque v nement transmis lobservateur est
estampill par HR
une observation de e est le couple (e, HR(e))
25
Observation valide
Au temps t, on d livre tous les messages
ayant des estampilles < t & dans lordre des
estampilles.
26
Caract risation des
observations valides
Condition de validit :
" Dans un syst me o les observations sont
ordonn es par des estampilles H, une condition
suffisante de validit est :
e e' H(e) < H(e') : condition de validit faible
de lhorloge (implication dans un seul sens)
Cette condition est trivialement satisfaite par HR
27
Etat Global?
Pas de HR
Temps de propagation des messages nest pas
born
Objectif: construire un syst me dhorloges
assurant une observation valide, en respectant
la condition de validit faible
Labsence de borne & aura une cons quence
sur la compl tude, non sur la validit
28
Horloges logiques (Lamport)
Principe:
chaque site i, un compteur HLi valeurs
enti res
Un v nement e se produisant sur le site i est
dat par la valeur courante de HLi , soit HLi(e)
Un message m mis partir du site i porte
une estampille gale sa date d mission
29
Algorithme de Lamport
Initialisation :
HLi = 0
v nement local et denvoi :
HLi = HLi + 1
Envoi dun message m :
on envoie (m, Em), avec Em = HLi (apr s incr mentation)
R ception dun message (m, Em) :
HLi = max (HLi, Em) + 1
30
Exemple
HL satisfait la condition de validit faible :
e e' H(e) < H(e')
Mais H(e) < H(e') (e e').
Donc ou bien e' e, ou bien e' || e
31
Ordre strict et total
Lordre nest pas strict. Deux v nements
peuvent avoir la m me estampille: ils sont
alors causalement ind pendants. Si on veut un
ordre strict, il faut ajouter un crit re (en
Advertisement
g n ral on prend le num ro du processus)
Si e pi, e pj, alors
(HL(e), i) < (HL(e'), j) ssi HL(e) < HL(e') ou (HL(e)
= HL(e') et i<j)
32
Non-d tection des v nements
manquants
p1 re oit des messages des autres processus. On
souhaite quils lui soient d livr s dans lordre de leurs
estampilles.
D livrance de m2 (3) et r ception de m4 (8). Peut-on le
d livrer ?
33
Non-d tection des v nements
manquants
Les trois situations sont indistinguables avec
les HL
Plus g n ralement, si HL(e) < HL(e'), existe-t-il
e" tel que e e" e' ?
Question insoluble. Il sagit dune propri t
de vivacit (un v nement va-t-il arriver ?)
Risque dun v nement ne soit pas d tect .
34
Solution: les messages stables.
un message re u est stable si aucun message
portant une estampille inf rieure ne
parviendra au destinataire
d livrer un message que sil est stable
Attendre la r ception dun message de tous
les metteurs potentiels. Puis, les d livrer
dans lordre des estampilles.
Canaux FIFO (si non FIFO, cest possible
mais plus complexe)
35
Solution: les messages stables.
Conna tre tous les metteurs potentiels
Traiter la non r ception dun processus : envoyer
un message avec demande de r ponse (ping)
Pas de garantie pour la terminaison quelle soit en
temps fini. (Dans la pratique, on utilise un d lai de
garde, avec le risque dune arriv e tardive)
36
Horloges vectorielles
On cherche caract riser la d pendance
causale, en construisant un syst me de
datation H qui ait la propri t de validit forte
:
e e H(e) < H(e')
Applications
observation, mise au point (attribution dune cause
un effet)
communication causale, diffusion causale
contr le et maintien de la coh rence dinformations
(Ex: la reprise apr s une panne)
37
Horloges vectorielles: Fidge, Mattern
Id e
inclure le pass de l v nement mission dans lestampille H du
message
Principe
Horloge vectorielle / Site
Taille
Nombre de sites
But
Dater les v nements
Identique aux horloges logiques
38
Horloges vectorielles: Fidge, Mattern (1988)
Fonctionnement
Associer un vecteur Vi chaque site Pi
Init : Vi = (0, & , 0)
Ev nement local Pi
Vi = Vi +1
Emission dun message m estampill par Vm
Vi = Vi +1
Vm = Vi de l metteur
R ception dun message (m, Vm) par Pi
Vi = Vi +1
Vi = max(Vi , Vm ) pour j = 1..n, j i
39
Exemple
40
Horloge Vectorielle
41
Horloges vectorielles
42
Horloges vectorielles
43
Horloges matricielles
Synth se
Horloge logique ou scalaire
R duite un nombre
Ce que Pi conna t du syst me (Hi)
Horloge vectorielle
Vecteur dhorloges scalaires
Ce que Pi conna t de Pj (Hi )
Horloge matricielle
Matrice dhorloges
Ce que Pi conna t de ce que Pj conna t de Pk (Hi )
44
Horloges matricielles
Principe
Horloge matricielle/Site
nxn
Ev nement ei de Pi
Dat par la valeur courante de HMi
Envoi de message
Estampill par Hmi
S mantique
Interpr tation de HMi
Nombre de messages de Pj vers Pk dont Pi a
connaissance
45
Horloges matricielles
Ev nement local Pi
HMi = HMi + 1
Envoi de message vers Pj
HMi = HMi + 1
HMi = HMi + 1
R ception de (m,Em) par Pj
D livr que si tous les messages qui sont causalement
ant rieurs lui ont t d livr s
Em = HMi + 1
Pour tout k i,j: Em = HMi (messages des autres sites)
D livrance et MAJ horloges
HMi = HMi + 1
HMi = HMi + 1
Pour tout k i,j et pour tout l i: HMi = max(HMi ,
Em )
46
Exemple
47
48
Exercice dapplication
On consid re l'ex cution parall le repr sent e par la figure
ci-dessous, dans laquelle :
les lignes horizontales repr sentent les chelles de temps
de processus.
eij repr sente le j me v nement observable sur le
processus Pi.
les fl ches reliant les v nements de processus distincts
sont des changes de messages
TAF:
Appliquer lalgorithme de lhorloge matricielle sur les deux
syst mes r partis suivants.
49
Exercice dapplication
50
51
Exercice dapplication
1. Donner deux couples d' v nements concurrents.
2. Quels sont les v nements causalement d pendants de
e11 ?
3. Donner des exemples d v nements causalement
ind pendants.
4. Proposer un mod le de datation relatif cet exemple.
52
Horloges matricielles
Optimisations
les horloges matricielles sont co teuses (
O(n2) )
Diverses optimisations ont t propos es
partitionner le syst me en sous-syst mes
(interaction faible entre sous-syst mes) - r duit
Advertisement
n
exploiter des caract ristiques sp cifiques du
syst me (synchronisation)
restreindre la profondeur du pass
53
Etat dun Syst me R parti
Notion de Coupure
tat dun syst me r parti
Coupures
Coupures coh rentes
Propri t s des coupures
coh rentes
59
Plan
Introduction:
D finition, organisation, propri t s, &
Partie 1: Bases de lalgorithmique r partie
1. Etat dans un syst me r parti, ordre, temps,
2. Observation coh rente
3. Algorithmique r partie
Partie2: Tol rance aux pannes et aux fautes
1. Validation atomique
2. Groupes, diffusion, coh rence
3. Consensus, prise de d cision
60
D finition
Exclusion mutuelle
Contexte de plusieurs processus s'ex cutant en parall le
Acc s une ressource partag e par un seul processus la
fois
Exclusion mutuelle en distribu
Acc s une ressource partag e distante par un seul
processus la fois
Processus distribu s
Requ tes et gestion d'acc s via des messages chang s entre
les processus
N cessit de mettre en Suvre des algorithmes g rant ces
changes de messages pour assurer l'exclusion mutuelle
61
Rappel
Un processus est dans 3 tats possibles, par rapport
l'acc s la ressource
Demandeur : demande utiliser la ressource,
entrer dans la section
Dedans : dans la section critique, utilise la ressource
partag e
Dehors : en dehors de la section et non demandeur
d'y entrer
62
Changement d' tat par un
processus
De dehors demandeur pour demander acc der
la ressource
De dedans dehors pour pr ciser qu'il lib re la
Ressource
Le passage de l' tat demandeur l' tat dedans est
g r par le syst me et/ou l'algorithme de gestion
d'acc s la ressource
63
Plusieurs grandes familles de
m thodes
Contr le par un serveur qui centralise les
demandes d'acc s la ressource partag e
Contr le par jeton
Un jeton circule entre les processus et donne l'acc s la
ressource
La gestion et l'affectation du jeton et donc l'acc s la
ressource est faite par les processus entre eux
Deux approches : jeton circulant en permanence ou
affect la demande des processus
Contr le par permission
Les processus s'autorisent mutuellement acc der la
ressource
64
Plusieurs grandes familles de
m thodes
Contr le par un serveur centraliseur
Avantages
Tr s simple mettre en Suvre
Simple pour g rer la concurrence d'acc s la
ressource
Inconv nients
N cessite un l ment particulier pour g rer
l'acc s
Potentiel point faible, goulot d' tranglement
65
Plusieurs grandes familles de
m thodes
Contr le par jeton
Principe g n ral
Un jeton unique circule entre tous les processus
Le processus qui a le jeton est le seul qui peut
acc der la section critique
Versions de lalgorithme
Anneau sur lequel circule le jeton en permanence
Jeton affect la demande des processus
66
Plusieurs grandes familles de
m thodes
Contr le par jeton sur anneau
un processus re oit le jeton
S'il est dans l' tat demandeur : il passe dans l' tat
dedans et acc de la ressource
S'il est dans l' tat dehors, il passe le jeton son voisin
Quand le processus quitte l' tat dedans, il passe le
jeton son voisin
67
Contr le par jeton sur anneau
Avantages
Tr s simple mettre en Suvre
Int ressant si nombreux processus demandeurs de la ressource
quitable en terme de nombre d'acc s et de temps d'attente
Aucun processus n'est privil gi
Inconv nients
N cessite des changes de messages (pour faire circuler le jeton)
m me si aucun site ne veut acc der la ressource
Temps d'acc s la ressource peut tre potentiellement long
Si le processus i+1 a le jeton et que le processus i veut acc der
la ressource et est le seul vouloir y acc der, il faut que le jeton
fasse tout le tour de l'anneau
68
Contr le par jeton avec
communication entre processus
Soit N processus avec un canal bi-directionnel entre chaque
processus
Canaux fiables mais pas forc ment FIFO
Localement, un processus Pi poss de un tableau nbreq, de taille N
Pour Pi, nbreq [ j ] est le nombre de requ tes d'acc s que le
processus Pj a fait et que Pi conna t (par principe il les conna t toutes)
Le jeton est un tableau de taille N
jeton [ i ] est le nombre de fois o le processus Pi a acc d la
ressource
La case i de jeton n'est modifi e que par Pi quand celui-ci acc de la
ressource
69
Contr le par jeton avec communication entre
processus (suite)
Initialisation
Pour tous les sites Pi : " j [ 1 .. N ] : nbreq [ j ] = 0
Jeton " j [ 1 .. N ] : jeton [ j ] = 0
Un site donn poss de le jeton au d part
Quand un site veut acc der la ressource et n'a pas le jeton
Envoie un message de requ te tous les processus
70
Contr le par jeton avec communication entre
processus (suite)
Quand processus Pj re oit un message de requ te venant de Pi
Pj modifie son nbreq localement : nbreq [ i ] = nbreq [ i ] + 1
Pj m morise que Pi a demand avoir la ressource
Si Pj poss de le jeton et est dans l' tat dehors
Pj envoie le jeton Pi
Quand processus r cup re le jeton
Il acc de la ressource (passe dans l' tat dedans)
71
Contr le par jeton avec communication entre
processus (suite)
Quand Pi lib re la ressource (passe dans l' tat dehors)
Met jour le jeton : jeton [ i ] = jeton [ i ] + 1
Parcourt nbreq pour trouver un j tel que :
nbreq [ j ] > jeton
Une demande d'acc s la ressource de Pj n'a pas
encore t satisfaite : Pi envoie le jeton Pj
Si aucun processus n'attend le jeton : Pi le garde
72
Advertisement
Contr le par Permission
Un processus demande l'autorisation un sous-
ensemble donn de tous les processus
Deux modes:
Permission individuelle : un processus peut donner
sa permission plusieurs autres la fois
Permission par arbitre : un processus ne donne sa
permission qu' un seul processus la fois
Les sous-ensembles sont con us alors tel qu'au moins un
processus soit commun 2 sous-ensembles : il joue le
r le d'arbitre
73
Permission individuelle
un processus peut donner sa permission
plusieurs autres la fois
Chaque processus demande l'autorisation tous
les autres (sauf lui par principe)
Liste des processus interroger par le processus Pi pour
acc der la ressource : Ri = { 1, ... , N } { i }
74
Permission individuelle
Se base sur une horloge logique (Lamport) pour
garantir le bon fonctionnement de l'algorithme
Ordonnancement des demandes d'acc s la ressource
Si un processus ayant fait une demande d'acc s re oit une
demande d'un autre processus avec une date ant rieure
la sienne, il donnera son autorisation l'autre processus
75
Algorithme de
Chaque processus g re les variables locales suivantes:
Une horloge Hi
Une variable dernier qui contient la date de la derni re
demande d'acc s la ressource
L'ensemble Ri
Un ensemble d'identificateurs de processus dont on attend
une r ponse : attendu
Un ensemble d'identificateurs de processus dont on diff re le
renvoi de permission si on est plus prioritaire qu'eux : diff r
Initialisation
Hi = dernier = 0
diff r = , attendu = Ri
76
Algorithme de
Si un processus veut acc der la ressource, il ex cute
Hi = Hi + 1
dernier = Hi
attendu = Ri
Envoie une demande de permission tous les processus de Ri avec
estampille (Hi, i )
Se met alors en attente de r ception de permission de la part de tous les
processus dont l'identificateur est contenu dans attendu
Quand l'ensemble attendu est vide, le processus a re u la permission de tous
les autres processus
Acc de alors la ressource partag e
Quand acc s termin
Envoie une permission tous les processus dont l'id est dans diff r
diff r est ensuite r initialis (diff r = )
77
Algorithme de
Quand un processus Pi re oit une demande de permission de
la part du processus Pj contenant l'estampille (H, j)
Met jour Hi : Hi = max (Hi, H) +1
Si Pi pas en attente d'acc s la ressource : envoie permission Pj
Sinon, si Pi est en attente d'acc s la ressource
Si Pi est prioritaire : place j dans l'ensemble diff r
On lui enverra la permission quand on aura acc d la ressource
Si Pj est prioritaire : envoi permission Pj,
Pj doit passer avant moi, je lui envoie ma permission
La priorit est d finie selon la datation des demandes d'acc s la ressource
de chaque processus
Le processus prioritaire est celui qui a fait sa demande en premier
Ordre des dates : l'ordre << de l'horloge de Lamport :
( dernier, i ) << ( H, j ) si ( ( dernier < H ) ou ( dernier = H et i < j ) )
78
lection
Probl me
Parmi un ensemble de processus, en choisir un
et un seul (et le faire conna tre tous)
s curit : un seul processus lu
vivacit : un processus doit tre lu en temps fini
L lection peut tre d clench e par un
processus quelconque, ventuellement par
plusieurs processus
Lidentit de l lu est en g n ral indiff rente,
on peut donc (par exemple) choisir le
processus qui a le plus grand num ro
Difficult : des processus peuvent tomber en
panne pendant l lection
lection
Utilit et domaines dapplication
Reg n ration dun jeton perdu : un jeton et un
seul doit tre recr
Dans les algorithmes de type ma tre-esclave :
lire un nouveau ma tre
en cas de d faillance du ma tre courant
lection
Algorithme de base: Bully algorithm
Algorithme de la brute
Hypoth ses
R seau fiable et synchrone
Identit des processus connue par tous
Principe
Bas sur la recherche dun min ou max dun
ensemble
Demande d lection par inondation
R ponse ceux qui ont un num ro inf rieur
le Processus est lu sil ne re oit aucune r ponse
lection: algorithme de la brute (bully)
Election sur un anneau (Chang et
Roberts)
83
Terminaison (1)
Mod le de calcul r parti (rappel)
Ensemble de processus communiquant par messages ; tat actif
ou passif
Programme (cyclique) de chaque processus :
loop
1. attendre un message (passage temporaire l tat passif)
2. ex cuter un calcul local en r ponse ce message
3. le calcul peut comporter lenvoi de messages dautres processus
ou la terminaison du processus (passage d finitif l tat passif)
end
Probl me de la terminaison
V rifier que le calcul est achev
Cela implique deux conditions sur l tat global du syst me
Tous les processus sont au repos (passifs)
Aucun message nest en transit
En effet larriv e dun message en transit peut relancer le calcul
r parti
Terminaison (2)
M thodes pour d tecter la terminaison
1. M thode g n rale : analyse de l tat global
La terminaison est une propri t stable
On peut donc la d tecter par examen dun
tat global enregistr (Partie 1 du cours)
2. M thodes sp cifiques : applicables un
sch ma particulier de communication
Sur un anneau
Sur un arbre ou un graphe orient (avec arbre
couvrant)
Terminaison sur un anneau
Principe :
visiter lanneau dans le sens de la
communication et v rifier que tous
les sites sont passifs apr s un tour
complet
Difficult :
un message mis apr s le passage du
visiteur (et non visible par celui-ci)
peut venir r activer (derri re lui) un
site trouv passif
Terminaison sur un anneau
(Misra)
Terminaison sur un anneau
(Misra)