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.
part of the document
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)
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 dun message m' dépendait causalement de la diffusion dun message m, alors un processus correct qui délivre m' délivrera m avant m'.
Montrez à laide dun chronogramme quon peut avoir une diffusion causale avec un ordre qui nest pas total. (1,5 pts)
Causale : Si la diffusion dun message m' dépendait causalement de la diffusion dun 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).
Quelle est la relation entre lordre FIFO et lordre total ? (1 pt) Aucune relation !
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).
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 :
Il est composé de 2 cases pour la saisie des opérandes et un groupe de 4 cases à cocher pour le choix de lopé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 dafficher le résultat de lopération dans la même jsp cest-à-dire dans index.jsp. (3 pts)
Un exemple daffichage est comme suit :
Dans la suite de index.jsp :
=
Exercice 2 : (8 pts)
Soit lalgorithme 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 lidentifiant 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 luid le plus grand ou le plus petit ? Expliquez. (1 pt)
Cest celui qui a luid 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 luid le plus grand va être toujours envoyé dans lanneau afin de revenir après un certain tours au même processus afin quil détecte que cest 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 cest aussi le sens de la circulation des messages). (2 pts)
Il y a 4 tours ; 0,5 par tours !!
3. Ainsi présenté, lalgorithme 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 à linté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 dassurer la terminaison de lalgorithme 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 (nimporte 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 (nimporte 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 lalgorithme. Pour N processus, on a besoin de N tours pour désigner lélu, ensuite 1 tours pour terminer lalgorithme donc en tout (N+1) tours, sachant que le tours contient N messages donc la complexité est en INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/fr/math/c/d/6/cd641c6cabc83e0f7ff510bf812feca1.png" \* MERGEFORMATINET . N*N+N messages exactement.
