M2 Info Paris 7 Algo Répartie - Examen 2018-2019 Eléments de corrections (non officiels, à lire d'un oeil critique !) == Exercice 1 == 1) Dans l'algorithme de la Figure 1, combien de processus décident ? => Chaque processus envoie des messages à tous ses voisins, et décide lorsque tous ses voisins lui ont envoyé un message. Si la communication est sans perte de messages, alors tous les processus décident. Donc N processus décident. 2) L'algorithme de la Figure 1 est-il un algorithme de vague ? => Non, en tout cas pas pour n'importe quelle struture de graphe. Par exemple, si le graphe comporte 2 processus non reliés, ou 3 processus en ligne, alors ce n'est pas un algo de vague : la décision de certains processus ne sera pas causalement après le début de tous les autres processus. 3) Si le graphe G est complet, l'algorithme de la Figure 1 est-il un algorithme de vague ? => Oui. Si le graphe est complet, alors la décision de chaque processus est bien causalement après le début de tous les autres (car chaque processus aura reçu un message de tous les autres). == Exercice 3 == Remarque : Pour cet exercice, je suppose qu'on a un système de rondes synchronisées, et que les processus peuvent distinguer leur successeur et leur prédécesseur, comme dans le devoir n°2 (le sujet de l'examen ne précise pas le contexte exact). 1) Est-il possible de faire une élection déterministe ? => Non. Sans génération de hasard, même dans un anneau avec 2 processus, on ne pourra jamais casser la symétrie entre les 2. 2) Est-il possible de faire une élection probabiliste ? => Oui et Non. Comme vu dans le devoir n°2, on peut tirer à Pile ou Face et supposer qu'il ne restera plus qu'un seul candidat au bout d'un certain temps. Mais sans connaître la taille de l'anneau N, il ne pourra jamais déterminer s'il est le seul candidat ou non. 3) Est-il possible de faire un algorithme déterministe qui permet à chaque processus d'obtenir le nombre de processus ? => Non. Pour avoir le nombre de processus il faudrait un algo de vagues. Mais on ne peut pas utiliser l'algo de prob/echo car on n'a pas de processus distingué (pas de leader) ni celui des phases car on ne connait pas la taille de l'anneau (donc on ne connait pas le diamètre du graphe). On n'a aucune des conditions nécessaires pour lancer un algo de vague. Ici, les processus ne pourraient même pas distinguer s'ils sont dans un anneau de taille 2 ou de taille 3. 4) Est-il possible de faire un algorithme d'élection probabiliste si les processus connaissent N ? => Oui. Comme vu dans le devoir n°2, on peut les faire tirer à Pile ou Face jusqu'à ce qu'il n'y ait plus qu'un seul candidat, et faire passer en même temps un compteur pour tester s'il reste plusieurs candidats : les non-candidats incrémentent le compteur en le passant, et si le compteur revient avec une valeur de N, alors le candidat sait qu'il est seul. == Exercice 4 == 1) Existe-t-il un algorithme qui satisfait les propriétés suivantes ? Accord, Validité et Terminaison ? => Non. Même avec 2 seulement processus, ils ne pourront jamais être sûr de décider la même valeur s'ils ne savent pas combien de messages peuvent se perdre. C'est le problème de l'"Attaque Coordonnée". 2) Existe-t-il un algorithme qui satisfait les propriétés suivantes ? Accord, Validité et Terminaison Faible ? => Si les processus savent qu'il n'y a pas de panne, alors c'est possible. Par exemple, avec seulement 2 processus, chacun envoie par message sa valeur à l'autre. Ils pourront donc avoir une liste de toutes les valeurs initiales ([0,0] ou [0,1] ou [1,1]). Il suffit ensuite qu'ils choisissent de la même façon (par exemple, choisir le + petit élément de la liste) pour décider la même valeur. On peut généraliser cette méthode à N processus, sur un graphe quelconque. On utilise un algorithme de vague (par exemple prob/echo si on suppose qu'il y a un leader) pour que tout le monde ait la même liste et puisse choisir de la même façon. == Exercice 5 == 1) Est-il possible de faire un algorithme de consensus déterministe tolérant au plus (n-1)/2 pannes par arrêt ? => Oui. Même si tous les processus tombent en panne sauf 2, il leur est toujours possible d'arriver à un consensus 2) Est-il possible de faire un algorithme de consensus déterministe tolérant au plus (n-1)/2 pannes byzantines ? => Non. Comme vu en cours, à partir d'un tiers de processus byzantins, il n'est pas toujours possible d'arriver à un consensus. Par exemple si on a 3 processus dont 1 byzantin, un processus "honnête" ne saura pas comment trancher entre l'autre processus "honnête" et le processus "menteur" (byzantin). Il ne pourra pas savoir lequel ment.