Corrigé - Algorithmes distribués
Contrôle Continu n°2
M1 ILC, ISI, RISE
Durée : 1h15
Documents interdits
1. Algorithme de Chandy et Lamport
1.1. Appliquer l’algorithme de Chandy et Lamport (dont le texte est rappelé en annexe 1), au
scénario suivant d'échange de messages entre trois processus P1, P2 et P3. Pour cela
compléter le tableau en annexe 2.
e
1
P1
P2
P2
e
4
M3
mk
2
mk
2
M1
e
2
e
3
e
5
e
7
e
10
e
15
mk
1
mk
1
e
11
e
14
M4
e
12
e
13
e
9
mk
3
e
6
mk
3
M2
e
8
Message M
Marqueur mk
Publicité
i
i
Remarque : pour chaque processus P1, P2, P3, « c(i) / reçu(i) » représente le contenu du canal
en entrée en provenance de Pi et « reçu(i) » le booléen associé à la réception du marqueur sur
ce canal.
Evénement
e1
e2
e3
e4
enreg_état1
FAUX
C(2)/reçu(2)
C(3)/reçu(3)
Action
enreg_état2 VRAI
D(mk2)
enreg. el2
C(1)/reçu(1)
C(3)/reçu(3)
Action
enreg_état3
C(1)/reçu(1)
C(2)/reçu(2)
Action
E(M1)
E(M2)
e6
e7
e5
VRAI
,V
, F
E(M3)
R(mk2), D( mk1)
enreg. el1
E(M4)
, F
{M1}, F
R(M1)
,
˘
˘
˘
Evénement
e8
e9
e10
e11
e12
e13
e14
enreg_état1
C(2)/reçu(2)
C(3)/reçu(3)
Action
enreg_état2
C(1)/reçu(1)
C(3)/reçu(3)
Action
Publicité
, V
{M2}, F
R(M2)
, V
{M2}, V
R(mk3)
envoi à Pc
{M3}, F
{M1}, F
R(M3)
{M3}, F
{M1}, V
R(mk3)
{M3}, V
{M1}, V
R(mk1)
envoi à Pc
enreg_état3 VRAI
C(1)/reçu(1)
C(2)/reçu(2)
, F
, V
Action
R(mk2), D( mk3)
enreg. el3
, V
, V
R(mk1)
envoi à Pc
1.2. On suppose que les états relevés par les processus sont envoyés à un processus collecteur
Pc qui recueille l'état global. Indiquer les état des canaux cij reçus par Pc .
cij
i=1
i=2
i=3
j=1
j=3
j=2
{M3}
{M2}
{M1}
2. Coupures cohérentes et estampillage vectoriel de Lamport
2.1. On associe un estampillage vectoriel de Lamport aux événements du scénario de
l'exercice 1. Indiquer les valeurs de toutes estampilles.
1
0
0
e
4
P1
2
1
0
e
5
3
1
0
e
7
Publicité
4
1
2
e
10
5
1
3
e
15
P2
e
1
P2
0
1
0
M3
mk
2
mk
2
M1
e
2
0
0
1
e
3
0
0
2
e
9
1
3
1
mk
3
e
6
0
2
1
mk
3
M2
e
8
0
1
3
1
4
3
e
11
mk
1
Publicité
mk
1
e
14
2
5
3
M4
e
12
2
1
4
e
13
3
1
5
˘
˘
˘
˘
˘
˘
˘
˘
˘
2.2. Indiquer la coupure (ei, ej, ek) correspondant aux états locaux enregistrés par P1, P2 et P3
qui ont été envoyés à Pc. Montrer que cette coupure est cohérente en utilisant la
caractérisation par l'estampillage vectoriel de Lamport.
C1= (e5, e1, e8)
EV(C1) = (2, 1, 3)
EV(e5) = (2, 1, 0) ; EV(e1) = (0, 1, 0) ; EV(e8) = (0, 1, 3) ;
On a bien EV(C1) = Max (EV(Ci)) pour i = 5, 1, 8
Donc la coupure est cohérente.
2.3. Donner un exemple de coupure incohérente en justifiant au moyen de l'estampillage
vectoriel de Lamport
Par exemple :
C2= (e10, e6, e2)
EV(C2) = (4, 2, 1)
EV(e10) = (4, 1, 2) ; EV(e6) = (0, 2, 1) ; EV(e2) = (0, 0, 1) ;
Ici EV(C2) < Max (EV(Ci)) pour i = 10, 6, 2 : (4, 2, 1) < (4, 2, 2)
Donc la coupure est incohérente.
2.4. Preuve : montrer que dans le cas général de n processus P1, … Pn reliés par des canaux
FIFO, l'algorithme de Chandy et Lamport garantit que l'état global (el1, el2, ... eln) envoyé au
processus Pc constitue une coupure cohérente. Pour cela vous pouvez raisonner par l'absurde.
Preuve
Supposons que la coupure correspondant à (el1, el2, ... eln) n'est pas cohérente. Cela signifie
qu'il existe un processus Pi, i ˛
réception d'un message M, dont l'émission n'est pas captée dans l'état elj du processus
émetteur Pj. Soit ejy l'événement correspondant à l'émission de M par Pj.
[1, n] tel que eli contient un événement eix correspondant à la
Puis que ejy n'est pas capté dans elj, cela signifie que ejy est postérieur à l'envoi du marqueur
mkj par le processus Pj (en effet l'envoi du marqueur a lieu lorsque le processus capte son état
local). Or les canaux étant FIFO par hypothèse, le marqueur mkj devrait atteindre le processus
Pi avant le message M, puisque son envoi est antérieur à celui de M. On aboutit donc à une
contradiction, puisque si tel était le cas, la réception de M par Pi serait postérieure à celle du
marqueur, et donc l'événement eix ne serait pas capté dans eli.
Donc la coupure ne peut pas être incohérente.