Exercice 1 : diffusion fiable, transaction et Election (7pt)

Correction EF 2015 - Algorithmique des systèmes et applications réparties
(M1 RSD) Question de cours : (7 pts) (1, 2 et 3 ne sont pas traités cette année) 1. Sans dessiner de chronogramme, expliquez la relation entre les
événements associés à 2 messages m et m' pour que la diffusion causale
soit respectée. (1,5 pts)
Si la diffusion d'un message m' dépendait causalement de la diffusion
d'un message m, alors un processus correct qui délivre m' délivrera m
avant m'.
2. Montrez à l'aide d'un chronogramme qu'on peut avoir une diffusion
causale avec un ordre qui n'est pas total. (1,5 pts)
[pic]
Causale : Si la diffusion d'un message m' dépendait causalement de la
diffusion d'un message m, alors un processus correct qui délivre m'
délivrera m avant m'. (Vrai : on peut examiner m1 et m3 : les seules
diffusions). Total : Si un processus correct délivre m avant de délivrer m', alors tous
les autres processus corrects délivreront m avant m'. (Faux, m2 est délivré
uniquement par P2 ! attention, on ne parle pas de diffusion ici). 3. Quelle est la relation entre l'ordre FIFO et l'ordre total ? (1 pt)
Aucune relation !
4. Avec 8 processus corrects et 2 processus fautifs, quel est le nombre
exact de messages échangés afin de réaliser un consensus dans un
environnement synchrone, fautes byzantines ? (1,5 pts)
9+9*8+9*8*7
Explication : ici, on peut faire le consensus. Pour 2 processus fautifs,
on doit avoir au minimum 5 processus corrects.
8+2=10 (le chef+ 9 processus). Le chef exécute P(2), chacun des 9
processus exécutera récursivement P(1) et P(0).
5. Même question pour 6 processus corrects et 3 processus fautifs. (1,5
pts)
Ici, on ne peut pas faire de consensus. Pour 3 processus fautifs, on a
besoin au moins de 7 processus corrects.
Exercice 1 : (5 pts) Soit le formulaire «calculatrice» suivant : [pic] Il est composé de 2 cases pour la saisie des opérandes et un groupe de 4
cases à cocher pour le choix de l'opération (+ est coché par défaut). 1. Ecrire index.jsp afin de réaliser le formulaire précédent. (2 pts) 0,25 pour Form, Table et TR.


0,25

+ 0,25
- 0,25
* 0,25
/ 0,25

0,25


0,25


2. Complétez index.jsp afin d'afficher le résultat de l'opération dans la
même jsp c'est-à-dire dans index.jsp. (3 pts) Un exemple d'affichage est comme suit : [pic]
Dans la suite de index.jsp :
= Exercice 2 : (8 pts) Soit l'algorithme d'Élection suivant, il tourne en parallèle dans tous les
processus et il est appliqué sur un anneau unidirectionnel :
etat = inconnu ;
u = uid; // uid est l'identifiant de chaque processus (uid >
0)
do {
send (u); // envoyer u au processus suivant
m = receive (); // recevoir u du processus précédent
if ( m > uid ) u = m;
if ( m < uid ) u = 0 ;
if ( m == uid ) etat = elu;
} while ( etat == inconnu );
1. Par rapport au code précédent, le leader (processus élu) est celui qui a
l'uid le plus grand ou le plus petit ? Expliquez. (1 pt) C'est celui qui a l'uid le plus grand.
Au départ, chaque processus envoie son uid au processus suivant et reçois
celui du processus précédent. La maj de u se fait par la suite.
if ( m > uid ) u = m; veut dire que l'uid le plus grand va être toujours
envoyé dans l'anneau afin de revenir après un certain tours au même
processus afin qu'il détecte que c'est lui l'élu. 2. Exécutez cet algorithme sur un anneau unidirectionnel qui contient 4
processus qui ont comme uid 9, 21, 30 et 16 respectivement. (9, 21, 30, 16
c'est aussi le sens de la circulation des messages). (2 pts) Il y a 4 tours ; 0,5 par tours !! [pic] 3. Ainsi présenté, l'algorithme ne se termine pas pour tous les processus,
pourquoi ? (1 pts) Seul le processus élu se termine car il a : etat = elu, tous les autre
processus bouclent à l'intérieur du do ; while car leurs variables etat
reste toujours inconnu. A certain moment, ils sont aussi bloqués par le
receive () à cause de la terminaison de l'élu.
4. Modifiez le code précédent afin d'assurer la terminaison de l'algorithme
pour tous les processus. (2 pts) etat = inconnu ;
u = uid;
do {
send (u);
m = receive ();
if (m==-1) //1,5
{
send (m) ;
System.exit(0) ; // forcer la terminaison
}
if ( m > uid ) u = m;
if ( m < uid ) u = 0 ;
if ( m == uid ) etat = elu;
} while ( etat == inconnu );
id=-1 ; //0,5
send(id) ; Explication : L'élu envoie -1 au processus suivant (n'importe quel entier <
0 est valable car uid >0), ce dernier envoi à nouveau -1 à son suivant et
se termine et ainsi de suite pour les autres processus (n'importe quelle
autre instruction pour forcer la terminaison est acceptée). 5. Quelle est la complexité de cet algorithme ainsi proposé ? (2 pts) Pour 4 processus, on fait 4 tours pour désigner l'élu et un tour
supplémentaire pour terminer l'algorithme. Pour N processus, on a besoin de
N tours pour désigner l'élu, ensuite 1 tours pour terminer l'algorithme
donc en tout (N+1) tours, sachant que le tours contient N messages donc la
complexité est en [pic]. N*N+N messages exactement.