ÉCOLE NATIONALE D’INGÉNIEURS ENI-ABT
DER: Génie Informatique et Télécommunication (GIT)
UE: Systèmes Distribués CLASSE: M1S2
03-12-2024
TD N° 2
Exercice 1
L’objectif est de comparer deux évènements e1 et e2 qui se passent dans deux sites différents. Nous
supposerons que l’évènement e1 (resp. e2) est un évènement local du site 1 (resp. 2).
a) Supposons que les deux sites ont une horloge de Lamport comme système de datation. Comparer
les deux évènements e1 et e2 dans les deux situations suivantes :
1. la date de l’évènement e1 est 4 et celle de e2 est 3.
2. la date de l’évènement e1 est 4 et celle de e2 est 4.
b) Supposons que les deux sites ont une horloge vectorielle comme système de datation et que le
système distribué est composé de trois sites. Comparer les deux évènements e1 et e2 dans les deux
situations suivantes :
1. la date de l’évènement e1 est (4, 3, 2) et celle de e2 est (5, 2, 1).
2. la date de l’évènement e1 est (5, 3, 6) et celle de e2 est (4, 2,5).
Exercice 2
On considère un système distribué constitué de 4 sites P1, P2, P3, P4, s’envoyant des messages de façon
asynchrone comme représenté par la figure suivante. Les événements d’un processus, représentés par des
gros points noirs, sont soit des événements locaux (étapes d’un calcul), soit des envois ou des réceptions
de messages.
Ces événements sont datés par un système d’horloges de Lamport, initialisées à 0 dans chaque état initial.
1. Indiquez au-dessus de chaque point de la figure, la valeur de l’horloge du processus où se produit
l’événement correspondant.
Ces événements sont datés par un système d’horloges vectorielles, initialisées à [0, 0, 0, 0] dans chaque
état initial.
2. Indiquez à côté de chaque point de la figure la valeur de l’horloge du processus où se produit
l’événement correspondant.
3. On considère les événements a, b, c et d de la figure. Cochez toutes les formules justes :
∎𝑎 →𝑏 ∎𝑎 →𝑐 ∎𝑏 →𝑐 ∎𝑎 → 𝑑
∎𝑏 →𝑎 ∎𝑐 →𝑎 ∎𝑐 →𝑏 ∎𝑑 → 𝑎
∎ 𝑎||𝑏 ∎ 𝑐||𝑎 ∎ 𝑏||𝑐 ∎ 𝑎||𝑑
1/2
Exercice 3
On considère la figure suivante décrivant une exécution d'un calcul réparti :
1. Quel est le passé causal de r4 ?
2. Quel est le futur causal de r3 ?
3. Le chemin 𝑒1 → 𝑟2 → 𝑒5 → 𝑟4 → 𝑒7 → 𝑟6 est-il un chemin causal liant e1 à r6 ?
4. La coupure indiquée est-elle cohérente ? Pourquoi ?
5. L'état global x = 2 & y = 4 n'est pas survenu dans l'exécution présentée (x passe à 3 après l'événement
e3, et y passe à 4 après l'événement e6). Cet état est-il pourtant cohérent ?
6. Donner la valeur des horloges de Lamport pour tous les événements.
7. Déterminer l'histoire causale de m et en déduire si les délivrances r5; r3; r6; r7 respectent la causalité.
Exercice 4
On considéré les échanges de messages entre 3 sites A; B; C représentés par le chronogramme suivant :
1. Dans le chronogramme de la figure (1), quelle particularité implique que ce dernier ne représente pas
un calcul diffusant ?
2. Pourquoi certaines actions des processus (à préciser) ne peuvent pas être considérées dans ce
chronogramme comme atomiques ?
3. Les événements i2 et r5 sont-ils causalement liés ?
4. Donner une coupure cohérente incluant les événements i2 et e4.
5. Donner une coupure non cohérente incluant les événements i2 et e4.
6. Déterminer la valeur de l'horloge vectorielle de l'événement r4. Justifier cette valeur soit par
raisonnement, soit en calculant les horloges des événements le précédant.
7. Déterminer l'histoire causale du message m6 et en déduire si les délivrances r6; r7 respectent la
causalité.
2/2