Université Mohamed Khider Biskra
Faculté SESNV
Département d’informatique
Chargée TD: Dr. BAHI Naima Niveau: M1 Groupes: 3 et 5 Module: SD Année: 2020-2021
Correction Série d’exercices n°(
n°(2): Etat global des systèmes distribués.
distribués
Exercice 1
Schéma 1
Une coupure 𝐶 est l’ensemble des d’évè
d’évènements tels que si 𝑒 ∈ 𝐶 et (é précède ède localement e), alors é ∈ 𝐶.
Considérant schéma 1:
1. Deux événement a et b sont dits conçurent si l’exécution de l’un n’influe pas sur l’exécution de l’autre = il n’y a
aucune précédence causale entre eux. a || b ((a b) (ba)).
Les
es paires d’évènements concurrents dans lla liste donnée sont: a//b, h//u et r//x.
2. La coupure 𝐶 contient les évènements
nements {a, x, b, y, t, r}
r}.
𝑐𝑒𝑝𝑡𝑖𝑜𝑛)𝐶 𝑒𝑡 𝑞(é𝑚𝑖𝑠𝑠𝑖𝑜𝑛) ∈ 𝐶 . Car en utilisant la relation de causalité, on vérifie
3. 𝐶 est non-cohérente car 𝑣(𝑟é𝑐𝑒𝑝𝑡𝑖𝑜𝑛
pour chaque évènement de réception appart
appartient
ient à une coupure que son évènement d’émission n’appartient pas au futur.
Exercice 2
Schéma 2
1. Datation scalaire (voir le tableau suivant):
Evènement e11 e12 e13 e14 e21 e22 e23 e24 e31 e32 e33 e34
Horloge 1 2 3 4 1 2 3 6 1 4 5 6
2. Datation vectorielle (voir le schéma suivant):
3. Ordre global : e11, e21, e31, e12,e22,e13,e23,e14,e32,e33,e24,e34
4. Relation de causalité: Passé (e23)={e23,
{e23,e22,e21,e11},
Horloges scalaires: Passé (e23)={e23,
(e23)={e23,e11,e12,e21,e22,e31},
1
Horloges vectorielles: Passé (e23)={e23,
(e23)={e23,e21,e22,e11},
5. Deux avantages pour les horloges de Lamport:
- La taille d’estampille est constante c.à.d. pas de nécessité de connaitre le nombre de sites dans le système.
- Etablir un ordre total d’évènements.
6. Les horloges vectorielles reflètent la dépendance causale.
7. Y et Z cohérente, X incohérente. Justification: Deux méthodes peuvent être utilisées:
a. La causalité: vérification pour chaque évènement de réception appartient à une coupure que son évèn
évènement
d’émission n’appartient pas au futur.
Pour la coupure Y, il y a un seul évènement de réception 𝑒 sur P2 dont l’évènement d’émission correspondant est 𝑒
sur P1 tel que 𝑒 ∈ 𝑌.
𝑒 , 𝑒 , 𝑒 sont des évènements de réception appartenant à la coupure Z où leurs événements d’émission sont
respectivement 𝑒 , 𝑒 , 𝑒 . Chacun de ces derniers évènements appartient à la coupure Z ce qui indique qu’elle est
cohérente.
Maintenant la coupure X est incohérente car 𝑒 ∈ 𝑃2 est un évènement de réception d’un message envoyé au
futur; 𝑒 𝑋.
b. Les horloges vectorielles
𝑒 : 3 1 0
Coupure X: X=<𝑒 , 𝑒 , 𝑒 >, 𝑒 : 1 4 3 𝑉 (𝑋).
𝑉 (X)=(3,4,3), 𝑉 (𝑋) = (3,4,2), 𝑉 (X)
𝑒 : 1 3 2
𝑒 : 1 0 0
Coupure Y: Y=<𝑒 , 𝑒 , 𝑒 >, 𝑒 : 1 2 0 𝑉 (Y)=(1,2,1), 𝑉 (𝑌) = (1,2,1), 𝑉 (Y)=𝑉
(Y)= (𝑌).
𝑒 : 0 0 1
𝑒 : 2 1 0
Coupure Z: Z=<𝑒 , 𝑒 , 𝑒 >, 𝑒 : 1 3 0 𝑉 (Z)=(2,3,2), 𝑉 (𝑍) = (2,3,2), 𝑉 (Z)=𝑉
(Z)= (𝑍).
𝑒 : 1 3 2
8. Il n’y a pas une violation de causalité (non respect de délivrance causale des messages) car tous pairs d’évènements
de réceptions sur le même site respectent
ctent le même ordre d’émission.
9. Dans le schéma suivant, on a un exemple
xemple de violation de l’ordre causal: 𝑒 devrait arriver avant 𝑒 . Ce dernier est
mis en attente et ne sera délivré qu’aprè
qu’après 𝑒 .
Justification: Sur le site S2, on a deux évènements de réception 𝑒 et 𝑒 tel que 𝑒 𝑒 (ordre de réception) mais
émission ne respectent pas le même ordre 𝑒 𝑒 (𝑒 𝑒 𝑒 𝑒 ).
leurs évènements d’émission
