Corrigé - Algorithmes distribués

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

, 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

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

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.