Sétif le 13-01-2015

Université Ferhat Abbas Sétif 1

Faculté des sciences
Département d'Informatique Module Algorithmes Distribués (MTC)
Tous documents autorisés (Toute communication de documents entre étudiants est interdite)

Problème. Soient trois processus P1, P2 et P2 situés respectivement sur trois machines M1, M2 et M3
interconnectées via un réseau de communication de type Ethernet, et soit le chronogramme d’exécution suivant :
P1 e11 e12

P2 e21 e22

P3 e31 e32
a)
1. En supposant qu’à l’initialisation, les valeurs des horloges matricielles des processus soient nulles, donnez les
valeurs des estampilles des évènements e21, e32, e12 1,5 pts.
100 000 202
Réponse : e21 110 e32 000 e12 000
000 002 002
2. A quel problème peut-on faire face lors de l’utilisation des horloges matricielles et comment réduire ce
problème ? 01 pt
Réponse : - Le problème dans l’utilisation des horloges matricielles est l’encombrement des messages produit
par la transmission des estampilles lorsque celles-ci sont de tailles importantes. La matrice véhiculée par les
messages occupe une grande partie de l’espace d’un message qui devient inacceptable.
- On peut réduire cet encombrement en ne transmettant que les valeurs des estampilles qui ont changé depuis
le dernier envoyé vers un même processus.
3. En supposant qu’après les évènements e12, e22 et e32, les trois processus P1, P2 et P3 décident 02 pts
simultanément d’accéder à un objet exclusif Obj, donnez l’ordre d’accès à Obj et justifiez votre réponse.
Réponse : L’accès à Obj de manière exclusive nécessite l’application d’un algorithme d’exclusion mutuelle,
comme par exemple l’algorithme de Lamport qui utilise les horloges scalaires. Ainsi, chaque processus Pi, 1≤
i≤ 3 envoie sa requête req avec la valeur de son horloge locale et son identité, par exemple lors de l’évènement
e13 : req(1,3), e23 : req(2,3) et e33 : req(3,2). Ce qui donne, selon l’application de l’algorithme de Lamport,
l’ordre d’accès : P3, P1 puis P2.
b) Chacune des machines Mi du réseau est munie d’une horloge physique Hi,
1. Pourquoi a t-on besoin de synchroniser ces horloges ? Donnez deux situations où la synchronisation des
horloges est indispensable. 1,5 pts
Réponse : - Parce que les horloges dérivent quelque soit leur degré de performance ; les synchroniser revient
à les mettre presque au même temps.
- Utilisation indispensable de la synchronisation dans le protocole de communication TDMA, ou
- Gérer les dates d’entrée et sortie dans un parking via plusieurs accès, pointage des ouvriers d’une grande
usine à plusieurs accès, ou créer des checkpoints locaux au même moment, etc.
2. Si toute paire d’horloges Hi, Hj dérivent l’une de l’autre de 1 seconde toutes les 500 secondes, une période
de resynchronisation de 200 ms est-elle suffisante pour limiter l’inclinaison à 2 ms ? dans le cas contraire
que faut-il faire ? 02 pts
Réponse : Au bout de 500 s, les horloges dérivent de 1s (ou bien 500 000ms dérivent de 1000 ms), quelle
sera la dérive au bout de 200 ms soit (1/500)*200=2/4=0,5 ms < 2 ms, ce qui est largement suffisant. Si la
dérive était supérieure à 2 ms alors il faudrait diminuer l’intervalle de resynchronisation.

3. Existe-t-il une relation entre la synchronisation des horloges physiques et la causalité des évènements dans un
système distribué qui manipule le temps physique ? Discutez. 01 pt
 Réponse : Oui, car si on synchronise les horloges, c’est-à-dire le recaler, sans tenir compte du principe de
causalité, on pourrait avoir une perturbation de l’historique des évènements du système : des évènements qui
se sont produits normalement dans le passé se verront produits dans le futur après synchronisation. Par
exemple, si les horloges des accès d’un parking de stationnement son resynchronisées brutalement sans tenir
compte de la causalité des évènements, on pourrait avoir des entrées dans le parking après les sorties.
c) 1. Si le mode de défaillances des Mi est de type crash (Fail-stop), quel serait le nombre de messages
nécessaires pour arriver à un consensus ? 01 pt
Réponse : Pour un mode de défaillance fail stop, une machine en panne ne fournit aucun message donc aucun
message faux n’est émis. Donc toute autre machine qui désire connaître son état l’obtient sans passer par
l’obtention d’un consensus des autres machines, donc aucun message pour le consensus.
2. Même question que 1) précédent, si le mode de défaillance est de type byzantin ? 01 pt
Réponse : Dans un mode de défaillance byzantin et dans un système synchrone, le consensus est atteint lorsque
le nombre de processeurs défaillants f est tel que N ≥ 3f +1 avec N : nombre total de processeurs. Autrement
dit : si un des processeurs Mi est en panne, il faudra 4 au total pour avoir un consensus de sa défaillance ce
qui n’est pas possible puisqu’on a que 3 processeurs.

d) Les processus Pi, 1≤ i≤ 3, sont supposés connectés en anneau virtuel, et soient deux fichiers F1 et F2 pouvant
être utilisés en lectures ou en modifications ;
1. Donnez les procédures lecture et modif permettant à tout Pi, 1≤ i≤ 3, d’accéder à F1 et/ou F2 05 pts
Réponse : On associe aux lectures sur F1, 03 jetons de lecture : jetonlecF11,jetonlecF12, jetonlecF13 et 03
jetons de lectures sur F2 : jetonlecF21, jetonlecF22, jetonlecF23. Puis un jeton d’écriture pour chaque fichier
jetonecrF1 et jetonecrF2.
Procedure lireFi (i=1,2)
Begin
Attendre un jeton de lecture jetonlecFij
Prendre le jeton
< Lecture sur Fi>
Libérer jeton de lecture
End.
Procedure ecrireFi (i=1,2)
Begin
Attendre jetonecrFi
Prendre jetonecrFi
Attendre jetonlecFij (j=1,2,3)
< ecrire sur Fi >
Liberer jetonlecFij (j=1,2,3)
Liberer jetonecrFi
end

2. Montrez que votre solution satisfait la propriété de sécurité (safety) 02 pts

Réponse : La sécurité indique que « quelque chose de mauvais ne va jamais arriver ». Cette propriété concerne
les accès exclusifs. En effet, si 2 processus désirent modifier simultanément sur un fichier ou les deux, aucun
problème ne se produit. Toutefois, si P1 capture jetonecrF1 et attend jetonecrF2 et tous les autres jetons de
lectures pour modifier F1, et F2, P2 ou P3 ferait la même chose en capturant le jeton jetonecrF2 et attendant les
jetons de lecture ce qui conduit inévitablement à un interblocage.
La solution consiste à demander les jetons de modification toujours selon le même ordre lorsqu’on cherche à
modifier F1 et F2.

e) On considère maintenant que P1 produit des messages consommés par P2 et P3 ; Donnez l’expression abstraite
de synchronisation si le buffer de dépôt et de retrait de messages se trouve sur M2. 02 pts
Réponse : Soient nProd : nombre de productions et nCons le nombre de consommations.
 Pour pouvoir déposer un message dans le buffer il faut vérifier l’expression : nProd – nCons < N, et pour pouvoir
retirer un message, on doit vérifier l’expression suivante : nProd – nCons > 0 d’où l’expression abstraite de
synchronisation est :
nProd – nCons ≤ N
nProd – nCons ≥ 0
Et cela quelque soit le système producteur-consommateur. Dans le cas qui nous concerne, on a un producteur et
deux consommateurs, donc l’expression abstraite de synchronisation :
nProd - ∑nConsi ≤ N et (*)
nProd - ∑nConsi ≥ 0
Comme le producteur ne connait que le nombre de ses productions, nProd, il va demander aux consommateurs
cons2 et Cons3 de lui transmettre leurs consommations pour satisfaire l’expression
Nprod – (nCons2’ + nCons3’) < N pour pouvoir déposer un message dans le buffer.
De même, pour P2, il connaît que nCons2, il obtiendra nProd’ de P1 et nCons3’ de P3. Même chose pour P3, il se
fera envoyé nProd’ et nCons2’ et comme nProd ≥ nProd’ et nCons2 ≥ nCons2’, et nCons3 ≥ nCons3’ alors les
expressions précédentes (*) sont vérifiées.

N.B : La clarté des réponses est un élément d’appréciation !

Bonne copie !