TD – Systèmes Distribués
Etude de la diffusion
Master TI 1ère Année – UPPA – Eric Cariou
Exercice 1 : rappel sur un protocole d’ordre causal
Un protocole d’ordre causal est un protocole qui assure que les messages reçus sur un même
site sont délivrés en respectant les dépendances causales entre les événements d’émission de ces
messages.
Pour un message m, on notera em son événement d’émission, rm son événement de réception
et dm l’événement de délivrement du message, c’est-à-dire l’événement correspondant au moment
où le message sera réellement délivré au processus récepteur (le délivrement peut être décalé dans
le futur par rapport à la réception).
e11 e12
P1
m2 m1
e22
P2
e21
m3
P3
e31 e32
1. Mettre en évidence le non-respect des dépendances causales en émission pour le chrono-
gramme ci-dessus (ce chronogramme ne correspond pas à celui du système décrit à la page
précédente). Placer les événements de délivrement des messages sur le chronogramme en
respectant ces dépendances causales.
2. Déterminer la relation générale entre les événements associés à 2 messages pour que l’ordre
causal de leur émission soit respecté lors de leur délivrement.
3. Montrer que les horloges de Mattern ou de Lamport ne permettent pas de détecter le non-
respect des dépendances causales en émission et de bien ordonner les délivrances des mes-
sages.
4. Dater les événements via une horloge matricielle et préciser comment cela permet d’assurer
le respect des dépendances causales.
Exercice 2 : diffusion causale
Cet exercice est comparable au précédent mais cette fois dans le contexte de la diffusion de
messages. On considérera dans cet exercice des processus et des communications fiables.
Sur un chronogramme, on peut représenter la diffusion d’un message comme un ensemble de
sous-messages ayant un événement commun d’émission et un événement de réception pour chaque
1
e11 e13 e15 e16
P1
e12 m3 e14
m1
e22 e23 e25
P2
e21 e24
m2
m4
e35
P3
e31 e32 e33 e34
Figure 1: Chronogramme de l’exercice 2 : diffusion de messages
processus (y compris celui qui a lancé la diffusion). Le chronogramme de la figure 1 représente 3
processus qui communiquent via de la diffusion (4 diffusions sont réalisées ici : messages m1 , m2 ,
m3 et m4 ).
Un message m diffusé est caractérisé par les événements suivants :
– em qui est l’émission (la diffusion) du message
i
– Pour chaque processus Pi , rm qui est la réception du message par le système de communi-
cation de Pi
– Pour chaque processus Pi , dim qui est le délivrement du message à Pi par le système de
communication de ce processus
Le chronogramme ci-dessus représente uniquement les événements d’émissions le délivrement
immédiat d’un message dès sa réception, sans se préoccuper d’assurer des contraintes au niveau
de l’ordre de délivrement des messages.
La diffusion causale est une diffusion qui assure que si la diffusion (l’émission) d’un message
m0 dépend causalement de la diffusion d’un message m, alors tout processus délivre m avant m0 .
Questions :
1. Déterminer la relation entre les événements associés à 2 messages m et m0 pour que la
diffusion causale soit respectée.
2. Mettre en évidence sur le chronogramme de la figure 1 un non-respect des conditions de la
diffusion causale.
3. Dater les événements du chronogramme avec les horloges de Mattern. Est-ce que cette data-
tion permet de déterminer si la diffusion causale est respectée et le cas échéant de retarder
le délivrement d’un message ? Pourquoi ?
4. Proposer une version restreinte des horloges de Mattern où tous les événements ne sont pas
datés et qui permette d’assurer les conditions de la diffusion causale en pouvant retarder au
besoin le délivrement de messages. Expliciter la relation qui permet d’assurer le respect d’un
ordre causal ou d’un ordre FIFO.
5. Cette méthode de datation permet-elle d’assurer un ordre total ? Expliquer pourquoi une
méthode simple par datation ne permet pas de déterminer un ordre total.