Faculté des Sciences Exactes Année universitaire : 2020/2021
Département d’Informatique Durée : 01H30
Année d’étude : Master2, ReSyD Le 02 Mai 2021
EMD Systèmes Distribués 2
Exercice 01. (10 points)
Soit l'algorithme suivant de parcours (ou de diffusion) dans un réseau:
Algorithme de Pi
Lors de décision de Pinit de lancer un parcours
faire
reçui vrai ;
nb_acqi cardinal(voisinsi) ;
∀ j ∈ voisinsinit, envoyer(parcours, info, init) à Pj ;
fait
/*------------- séquences exécutées par le processus Pi --------- */
Lors de réception de (parcours, info, j)
faire
si reçui alors nb_acqi nb_acqi – 1 ;
sinon
reçui vrai ;
perei j ;
nb_acqi cardinal (voisinsi) - 1 ;
∀ j ∈ voisinsi – perei, envoyer (parcours, info, i) à Pj ;
fsi
si nb_acq = 0 alors envoyer(retour, info’) à perei fsi;
fait
Lors de réception de (retour,info’) par Pi
faire
nb_acqi nb_acqi – 1 ;
actualiser info’ ;
si nb_acqi = 0 alors
si i ≠ init alors envoyer(retour, info’) à perei ;
sinon terminé vrai ;
fsi
fsi
fait
1
Description des variables utilisées:
reçui : booléen initialisé à faux, qui indique si Pi a déjà été atteint par le parcours.
voisinsi : ensemble constant des voisins de Pi.
nb_acqi : contient, après que Pi a reçu l’information, le nombre
d’acquittements que Pi attend.
perei : le père de Pi
info : est diffusée par l’initiateur pour informer les autres sites de son
besoin de collecter des valeurs sauvegardées à leurs niveaux (exple : "je
veux collecter vos valeurs")
Info’ : est l’information collectée au fur et à mesure après sa mise à jour sur
chaque site.
Questions:
a. Quel est le type de parcours réalisé par cet algorithme?
b. Par rapport à la définition vu en cours, réalise-t-il un arbre couvrant ?
c. Dérouler l’algorithme sur le schéma suivant :
d. Supposons que la variable "info" informe les différents sites de l'intention de Pinit
de récupérer à travers " info' ", la somme des valeurs entières se trouvant dans
tous les autres. A la fin de l’algorithme, cette somme sera récupérée au niveau
de l’initiateur. Donner les modifications à apporter à l'algorithme afin de réaliser
cette tâche. (préciser juste l’endroit ou les instructions qu’il faut modifier)
2
Exercice 02. (7 points)
L'algorithme d'élection de Franklin fonctionne sur un anneau qui permet une
communication bidirectionnelle. Comparativement à l'algorithme de Chang-
Robert, il a une meilleure complexité en nombre de messages échangés. Les
processus avec les identificateurs différents sont disposés dans un ordre arbitraire
dans l'anneau. Il y a deux possibilités de couleurs pour chaque processus : blanc ou
noir. Au départ, chaque processus est blanc, ce qui implique que chacun est un
candidat à l’élection du maximum. L'algorithme est synchrone et fonctionne en
tours. Dans chaque tour, chaque processus blanc envoie un jeton contenant son
identifiant unique aux deux voisins et examine ensuite les jetons reçus d'autres
processus. Lorsque le processus i reçoit un jeton des processus j et j > i, il quitte la
course et devient noir. Un processus noir reste passif et agit uniquement comme
routeur (il fait juste passer les jetons). Comme les jetons sont envoyés dans les
deux sens, à chaque fois que deux processus blancs adjacents s'échangent, l'un
d'eux doit devenir noir. Dans chaque tour, une fraction des processus blancs
existants deviennent noirs. L'algorithme se termine lorsqu'il n'y a qu'un seul
processus blanc dans l'ensemble du système. C'est donc le leader.
L’algorithme d’un processus blanc i est le suivant :
Programme Franklin de i
Var jeton : id du processus,
couleur ∈{blanc, noir},
r : entier {le numéro de tour}
L(i) : est l’identité du leader
Initialement tous les processus sont en blanc, r=0, L(i)=∅
Pour chaque processus en blanc dans le tour r>=0 faire
envoyer jeton(i) à ses voisins ;
recevoir les jeton(j) de ses voisins ;
Si ∃ jeton : j > i → couleur := noir ;
[]∀ jeton: j < i → r := r + 1 {passer au tour suivant}
[]∀ jeton: j = i → L(i):= i {algorithme terminé}
Fsi
Fpour
3
1.
Dérouler l’algorithme sur le schéma
suivant avec des liens bidirectionnels.
Montrer la couleur de chaque processus
après la fin de chaque tour.
N. B. N’écrivez pas toutes les
étapes du déroulement. Une seule
figure pour chaque tour suffira.
2.
On veut maintenant faire l’élection 0
sur un anneau unidirectionnel. 5 2
Supposons que les liens vont dans le
sens des aiguilles d'une montre. Le
7 1
schéma précédent devient comme
suit (voir la figure). Avec le même
principe de l’algorithme sur un 6 3
réseau adapté à un anneau 9
unidirectionnel :
a) Combien de tours sont nécessaires pour élire le processus de l'identifiant le
plus élevé en tant que leader ? Montrez le schéma de chaque tour. Montrez les
messages échangés ainsi que les états des processus.
b) Expliquez brièvement ce qui se passe dans chaque tour.
Généralisation : Toujours dans le cas d’élection sur un anneau unidirectionnel.
3. Quelle est la situation du pire des cas pour l’élection, par rapport à l’ordre
des processus dans l’anneau ? dans ce cas combien de tours seraient
nécessaires ?
4. Même question pour le meilleur des cas ? Justifiez brièvement vos réponses.
Bon courage
4
Nom & Prénom: ..………………………………………………..
Exercice 3 (03 poin) Remplissez les espaces mentionnés par des rectangles sur l’Algorithme
suivant du Consensus de Chandra et Toueg :
Notes : N est le nombre de processus.
f est le nombre maximum de défaillances : f <N/2
Algorithme su Pi
Function Consensus(vi)
(1) ri 0; esti vi; tsi 0;
(2) while true do
(3) c (ri mod n)+1; ri ri + 1; % 1 ri < + ∞ %
%------ Phase 1 du tour r: pc retrouve la plus récente valeur estimée ----%
(4) case ( i ≠c) then send PHASE1(ri, esti, tsi) to pc
(5) ( i = c) then wait until (……………) PHASE1(ri,est,ts) messages ont été reçus);
(6) esti …………………………………………
(7) endcase
% ------------ Phase 2 ronde r: pc propose à tout le monde ----------------------%
(8) if ( i = c ) then broadcast PHASE2(ri, esti) endif;
(9) wait until (PHASE2(ri,v) a été reçu de pc ∨ c ∈ suspectedi);
(10) if (PHASE2(ri,v) reçu de pc) then esti ……… ……….. ;
tsi ……………….... endif;
%---------- Phase 3 de la ronde r : de tout le monde au pc (vote) ------------%
(11) sent PHASE3(ri,esti,tsi) to pc;
(12) if (i = c) then wait until ((n - f) PHASE3(ri,est,ts)
messages ont été reçus);
(13) if (au moins f + 1 messages sont tels que ts = ri)
(14) then esti ………………………. ;
decide( ………………… . );
(15) endif
(16) endif
Protocole de Chandra et de Toueg fondé sur ◊S
5
6