Sétif le 25-01-2020

Université Ferhat Abbas Sétif 1

Faculté des Sciences
Département d’Informatique
Contrôle du Module : Algorithmes Distribués, MTC, durée 01h30
Documents non autorisés, tout transfert d’objets entre étudiants est interdit
Tout plagiat (Copiage) sera sévèrement sanctionné !
Problème :
Soit une application distribuée composée de trois processus P1, P2 et P3, et considérons le
chronogramme suivant décrivant l’évolution de ces trois processus où les eij représentent les
évènements et les LSij la sauvegarde des états locaux.
P1 e11 LS11 e12 e13 erreur
M1

P2 LS21 e21 e22 e23 LS22

M2
M3
P3 LS31 e31 e32 LS32 e33

Questions :
a. 1. Appliquez l’algorithme BSS pour imposer la stratégie FIFO aux messages délivrés. 2 pts
Réponse : e11=(100), e12= (101), e13=(111)
e21=(100), e22=(110), e23=(111)
e31=(111), e32=(001), e33=(101)
2. Quelle est la cause possible de cette indépendance causale ? Justifiez votre réponse. 1 pt
Réponse : La cause possible de l’indépendance causale au niveau des émissions/réceptions est
due au fait que les messages n’empruntent pas le même chemin de la source à la destination.
Car à l’émission, même en choisissant le segment réseau le moins encombré, deux msgs qui se
suivent peuvent suivre des chemins différents et arriver à destination en ordre inverse.
b. On suppose que P1 gère un compte C1 de valeur 1500 $, P2 gère un compte C2 de valeur 2000$
et P3 gère un compte C3 de valeur 2000$. Les messages M1, M2 et M3 transportent
respectivement 100$, 200$ et 300$.
1. Caractérisez (Cohérents, Incohérents, fortement cohérents) les états globaux GS1=(LS11,
LS21, LS32), GS2=(LS11,LS22,LS31) et donnez leurs valeurs respectives. 0,5*4= 2 pts
Réponse : GS1=(LS11, LS21,LS32)=5300$, est un GS incohérent car le message m2 est
sauvegardé au niveau de LS32 mais non sauvegardé au niveau de l’émetteur (message
orphelin). Même chose pour GS2=7300$ : incohérent car M3 est orphelin.
2. Si une erreur se produirait après e13 quel serait la bonne ligne de reprise ? Justifiez.
Réponse : LR= (LS10, LS21, LS31) qui constitue un état fortement cohérent. 1 pt
c. On suppose que les trois sites ou processus sont organisés en anneau virtuel.
1. Donnez un algorithme simple d’élection d’un leader 2 pts
Réponse : Qui dit anneau virtuel, dit jeton. Une fois la défaillance du leader détectée, le
détecteur soit Pi envoie un jeton ELECTION contenant l’ID de Pi. A la réception du jeton par
Pj, Pj y insère son ID. lorsque le jeton revient au niveau de Pi (détecteur), Pi proclame le
leader en envoyant un message LEADER(ID).
On peut également considérer que l’ID du jeton sera remplacé par l’iD le plus grand. Ce sera
le site du plus grand iD qui détectera qu’il est leader et proclamera son rang. Mais ici le
nombre de messages sera plus grand.
2. En déduire la complexité en messages de votre algorithme. 1 pt
Réponse : Ici, le détecteur de N° i envoie n-i+1 msgs d’élection et n-i+1 msgs de
proclamation du leader soit au total 2(n-i+1).
d. Les trois sites Si, 1  i  3 sont respectivement munis chacun d’une horloge physique Hi.
1. Définir les termes inclinaison et taux de dérive par rapport à ces horloges 1 pt
 Réponse : Inclinaison : différence le lecture instantanée entre deux horloges. Taux de
dérive : différence entre une horloge et une horloge parfaite de référence.
2. Décrire une utilisation des horloges physiques dans les algorithmes d’élection de leader. 1 pt
Réponse : Les horloges physiques sont utilisées pour détecter la défaillance du leader
courant : Armer un timer et attendre une réponse lors d’une émission d’une requête de
présence. Si le timer épuise son décompte, à plusieurs tentatives, sans avoir reçu de
réponse du destinataire, alors ce dernier sera considéré comme défaillant.
3. Si on estime que ces horloges s’inclinent de 500 ms toutes les 500. 000 s quel sera l’intervalle
de resynchronisation si on accepte une inclinaison d’au plus de 10 ms ? 1 pt
Réponse : 0,5/500000*x=0,01= 1/500000*x=1/100 x=5000 s
4. Peut-on utiliser ces horloges physiques pour établir un ordre total des évènements dans
cette application ? justifiez votre réponse. 2 pts
Réponse : On pourra utiliser les horloges physiques pour établir un ordre total des
évènements seulement lorsque ces horloges seront synchronisées avec un délai de
resynchronisation en rapport avec l’incertitude acceptable au niveau de l’application.
e. Les trois sites précédents constituent maintenant un réseau local. 1,5 + 1,5= 3 pts
1. Quel serait le nombre de messages total transmis par les différents processeurs pour arriver
à un consensus lorsqu’un seul processeur tombe en panne en mode de défaillance byzantine.
Réponse : Aucun consensus ne sera atteint car le nombre total de serveurs devrait être de 4
2. Quel serait le nombre de messages nécessaires pour arriver à un consensus si on rajoute
deux autres sites ? Ce nombre serait-il différent sur le réseau Internet ?
Réponse : On a donc 5 sites. A l’ étape 1, on aura 4 messages càd (n-1), à l’étape 2 on aura
(n-1)(n-2) soit (5-1)((5-2) = 4*3 d’où au total 16 messages.
Aucun consensus n’est possible sur un système asynchrone comme Internet.
f. Les trois sites constituent maintenant un système S de serveurs répliqués. La probabilité de bon
fonctionnement de chaque serveur (ou site) est de 0,9.
1. Si on admet que le système S fonctionne correctement seulement lorsqu’au moins deux
serveurs fonctionnent correctement, quelle serait la probabilité de bon fonctionnement du
système global S ? 1,5 pts
Réponse : Soit P la probabilité de bon fonctionnement d’un serveur ; P=0,9. Le système
fonctionne correctement si 2 serveurs sont corrects et le troisième défaillant ou bien les
trois serveurs sont corrects. Numériquement on a : C23*P2(1-P)+ P3= 3*0,92(0,1) +
0,93=0,243+0.729=0,972
2. Quel serait le nombre de serveurs de S pour atteindre une disponibilité de 99,99 % dans le
cas où pour fonctionner correctement au moins un serveur doit fonctionner correctement ?
Réponse : Soit x ce nombre serveurs pour que S atteigne une disponibilité de 99,99%. S ne
fonctionnerait pas correctement lorsque tous les serveurs sont défaillants et cela avec une
x
probabilité de 0,1x. S fonctionnerait correctement avec une probabilité de 1-0,1 =99,99%
1-0,9999=0,1x 0,0001=0,1x ou bien 1/104 =1/10x . 1,5pts
Log(1/104) =Log(1/10x) Log(1) – 4log(10)= Log(1)-xLog(10), ce qui donne :
0-4=0-x d’où x=4 donc 4 serveurs.