TD1 SD 1819

Le 18 novembre 2018
Université Med Khider Biskra

Département d’informatique
Systèmes distribués (M1)

Année universitaire : 2018 – 2019
Série d’exercices N° 1 (Etat global d’un système réparti)
Exercice n°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).
1. 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 :
a. la date de l’évènement e1 est 4 et celle de e2 est 3.
b. la date de l’évènement e1 est 4 et celle de e2 est 4.
2. 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
a. la date de l’évènement e1 est (4 3 2) et celle de e2 est (5 2 1).
b. la date de l’évènement e1 est (5 2 4) et celle de e2 est (4 3 6).
3. Complétez le chronogramme suivant :
a. avec les horloges scalaires.

b. avec les horloges vectorielles correspondantes.
Exercice n°2 :
1. Définir la notion de coupure cohérente.
2. Pour l’exécution d’une application répartie proposée dans la figure 1, identifier les coupures
cohérentes. Justifier votre réponse.
Figure 1
Exercice n°3 :
On considère trois processus coopérants qui réalisent un algorithme quelconque et s’échangent des
messages. On s’intéresse à l’exécution de la figure 2. Toutes les horloges sont initialisées à 0.
Figure 2
1. Donnez les horloges logiques (Lamport) associées à chacun des évènements, et les valeurs
d’horloge véhiculées par les messages.
2. Donnez les horloges vectorielles (Mattern) associées à chacun des évènements, et les valeurs
d’horloge véhiculées par les messages.
Exercice n°4 :
On s’intéresse à une application répartie composée de 3 processus échangeant des messages. On note
respectivement send(m) et receive(m) l’émission et la réception d’un message m. On dit que les
communications sont CO (pour Causally Ordered) si, pour tout message m et m’, on a :
send(m)  send(m’)  receive(m)  receive(m’)
On considère l’exécution d’une application répartie représentée dans la figure 1. Cette exécution vérifie-t-
elle la propriété Causally Ordered (CO) ?
Figure 3
Exercice n°5 :
Soient deux protocoles de délivrance de messages lors de la communication entre les différents sites d’un
système distribué. Les primitives utilisées sont :
 Emission (i, m, k) : signifie qu’un site i envoie un message m vers le site k,
 Delivrance(m, k) : signifie la délivrance de message m sur le site k.
Formellement, on a les descriptions suivantes :

Protocole 1: Emission(i, m1, k)  Emission(i, m2, k)  Delivrance(m1,k)  Delivrance(m2, k)
Protocole 2: Emission(i, m1, k)  Emission(j, m2, k)  Delivrance(m1,k)  Delivrance(m2,k)
Où i, j, et k sont des sites et m1 et m2 sont deux messages.
1. Quel est le type de délivrance assuré par chacun des protocoles ? Justifier.
2. Considérons le schéma suivant,
 Pour chaque protocole, remplir le tableau ci-dessous par : (i) les paires de messages qui
correspondent à son application, si il respecte le schéma ou non et la justification.
Protocole Paires de Respect de schéma Justification

Protocole 1
Protocole 2
Exercice n°6 :
Le schéma ci-dessous représente le déroulement du temps sur trois sites ; chaque ligne horizontale
correspond à un site, le temps s’écoule de la gauche vers la droite. Chaque point noir correspond à un
événement. Chaque flèche correspond à un message envoyé d’un site à l’autre.
S1 e14 e15

e11 e12 e13
e25
S2 e23 e24
e21 e22
S3
e31 e32 e33 e34 e35
1. Si les sites utilisent des horloges scalaires. Indiquer à côté de chaque événement la date de celui-
ci et à côté de chaque flèche l’estampille du message correspondant.
2. Même question pour des horloges vectorielles.
3. Que peut-on déduire ?
4. Si les sites utilisent maintenant des horloges matricielles où les événements e11, e21 et e31 ne
sont pas les premiers exécutés par les sites et ils sont datés respectivement par :
, et .
5. Indiquer à côté de chaque événement la date de celui-ci et à côté de chaque flèche l’estampille du
message correspondant. Que peut-on conclure ?

TD1 SD 1819

Transféré par

Droits d'auteur :

Formats disponibles

TD1 SD 1819

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

TD1 SD 1819

Transféré par

Droits d'auteur :

Formats disponibles

Le 18 novembre 2018

Université Med Khider Biskra

Systèmes distribués (M1)

Série d’exercices N° 1 (Etat global d’un système réparti)

a. avec les horloges scalaires.

Formellement, on a les descriptions suivantes :

Protocole Paires de Respect de schéma Justification

S1 e14 e15

Vous aimerez peut-être aussi