Université de Batna2
Faculté des Mathématiques et Informatique
Département d’Informatique
Année Universitaire 2017/2018
Section : Master 2 RSD
SERIE de TD N° : 01
MODULE : ALGORITHMES DISTRIBUES
Exercice N°1:
Soit 4 processus interconnectés entre eux via des canaux et qui exécutent les séquences de
pseudo-code suivantes :
L’opération send(nb, Px) envoie la valeur de l’entier nb au processus Px.
L’opération nb = receive(Px) attend un message contenant un entier de la part du processus
Px. L’entier reçu est placé dans nb.
Q1. Dessiner le chronogramme correspondant à l’exécution en parallèle des 4 processus.
Q2. Dater chacun des événements en utilisant la méthode de l’horloge de Lamport.
Q3. Dater chacun des événements en utilisant la méthode de l’horloge de Mattern
(vectorielle).
Q4. Donner l’ordre total global défini par l’estampillage de Lamport.
Exercice 02 :
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.
1/2
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 :
Exercice 03 :
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).
Question : 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.
Question : 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, 2, 5) et celle de e2 est (4, 3, 6) .
2/2