1. Election sur un anneau unidirectionnel
2. Election sur un arbre couvrant

D'abord, comprenons ce que c'est qu'un anneau unidirectionnel : chaque machine à un, et un seul destinataire (dit “successeur”) pour ses messages, et une seule source. Cependant, l'anneau ne suit pas nécessairement une numérotation des machines, ni même des connections physiques (tant qu'il existe un chemin physique pour réaliser chaque lien).

Chaque machine peut être vue comme divisée en trois parties :

Remarque : au fur et à mesure que les services tels que “élection” et “exclusivité mutuelle” se standardisent, ils peuvent migrer de la partie “contrôle” de chaque application que s'en sert à la partie “natif”–opérations locales.

Eléction :

• intervient quand un processus la demande
• son démon n'a pas besoin de savoir pourquoi
• elle a une fin

Notre réponse doit préciser

• les hypothèses (ou contexte ou prémisses)
• la principe de la solution
• le protocole
• le coût, exprimé en nombre de messages
• sensibilité aux évènements imprévus

1. GC ¹⁾ unidirectionnel FIFO
2. P_{i_0} est le site initiateur

1. le site initiateur envoie un jeton avec un message (“élection”), son identifiant, sa capacité, et l'identifiant de la machine qui a cette capacité (elle-même).
2. chaque machine change ces deux derniers éléments si sa capacité est supérieur, et transmet le jeton à son successeur.
3. quand le jeton revient au point de départ, on a la réponse (et on réalise une Proclamation)

Dans ce cas, nous parlons de protocole, car c'est un ensemble de traitements d'évènements : initialisation, réception, proclamation, fin.

• initialisation P_{i_0} envoie le jeton [“election”, i_0, c_{i_0}, i_0] à son successeur.
• Réception
  • lorsque P_i reçoit un jeton [“election”, i_0, c_j, j], alors
    • si i==i_0 (premier élément) alors proclamation, c'est le résultat à l'élection qu'il initié
    • sinon
      • si c_i > c_j, P_i envoie [“election”, i_0, c_i, i] à son successeur
      • sinon P_i envoie [“election”, i_0, c_j, j] a son successeur
• Proclamation
  • P_{i_0} envoie le jeton [“proclamation”, i_0, c_j*, j*] à son successeur.
  • Lorsque P_i reçoit [“proclamation”, i_0, c_j*, j*]
    • si i==i_0 alors Fin
    • sinon P_i le transmet à son successeur
• Fin
  • P_{i_0} retourne le résultat de l'élection [c_j*, j*] au demandeur.

• Demande simultanée

Tanenbaum et Van Steen propose un algorithme qui est basé sur l'envoi de messages, pas un jeton.

• les processus sont ordonnés, physiquement ou logiquement, de sorte que chaque processus connait son successeur.
• les processus connaissent tous les processus et l'orde dans lequel ils communiquent.

• lorsqu'un processus constate que le coordinateur semble hors service, il envoi un message ELECTION à son successeur.
• si son successeur est hors service, il l'envoie au successeur du successeur, jusqu'à trouver un survivant.
• lors de reception, chaque machine s'inscrit (numéro et capacité) dans le message.
• lorsque le message reviendra au point de départ, il contiendra la liste ordonnée des processus en service et leurs capacités. Après sélection du mieux, le message est transformé en COORDINATOR et circulé un tour, puis retiré.

• deux messages peuvent être lancés en même temps, plus ou moins : ça coute un peu en messages, mais au final les deux contiendront les mêmes informations et conduiront au même choix.

Il est coutume de distinguer trois “solutions” à ce problème:

• l'initiateur est la racine
• l'initiateur demande à la racine de conduire l'élection pour lui
• l'initiateur (et le protocole) ne s'appuient pas sur le rôle de la racine.

Topologiquement, si l'on oublie les notions de parent et fils et les remplace (initialement) par la notion fusionnelle voisins, tout processus peut être vu comme la racine d'une élection qu'il initie. Après, le processus duquel chaque processus reçoit le message ELECTION est logiquement son parent vis-àvis de ce scrutin, et ses autres voisins sont logiquement ses fils pour ce scrutin. Mais puisqu'il peut être difficile d'exprimer le protocole en ces termes inhabituels, on explicitera chaque fois “s'il recoit de son parent…s'il recoit d'un fils, il fait pour tous les autre fils mais pas le fils source…etc”

• GC : arbre couvrant, FIFO
• P_{i_0} : site initiateur

• le site initiateur envoie un jeton message de sondage à chacun de ses voisins ²⁾, et crée une liste pour contrôler les remontées.
• à réception, chaque site
  • change le jetonmessage si sa capacité est supérieur
  • continue la diffusion s'il peut (il n'est pas feuille)
  • remonte sa réponse s'il est feuille, ou si tous ses dépendants lui ont répondu, ayant sélectionnée la plus forte réponse au fur et à mesure que ses dépendants lui ont répondu.
• lorsque le site initiateur a reçu toute les remontées, il peut proclamer.
• le jeton, hormis le mot-clé “élection”, contient ID et capacité de la plus forte machine, et une pile qui commence par le “parent” de la demande (pour qu'il reconnaisse son élection) et de chaque machine l'ayant transmis pour qu'il sachent s'ils reçoivent des remontées (ils ont déjà vu) ou de nouveaux sondages.

1. P_{i_0} transmet le jetonmessage [ "election";c_{i_0},i_0; i_0 ] à tous ses voisins, tout en créant une liste de ceux-ci pour pouvoir pointer les remontées.

Lorsque P_j reçoit un jetonmessage [ "election";c_{i},i; \underbrace{i_0,...}_{pile} ]:

• Si P_i \notin pile ⇒ il s'agit d'une diffusion et non une remontée.
  • si c_j \gt c_i alors il modifie le jeton tel:[ "election";c_j,j; i_0,...,j ]
  • sinon, il modifie le jetonmessage tel : [ "election";c_i,i; i_0,...,j ]
  • s'il est feuille, il renvoie à son prédécesseur dans la file
    • sinon, il transmet à tous ses voisins hormis son prédécesseur dans la pile (celui duquel il a reçu la demande), et crée une liste pour pointer les remontées.
• Si P_i \in pile ⇒ il s'agit d'une remontée.
  • si c'est le premier retour, P_i le stocke
    • sinon, P_i le compare au jeton stocké, et remplace celui-là par le nouveau si la capacité indiquée dans le nouveau est supérieur.
  • P_i supprime le répondant de la liste de contrôle des remontées et le pop de la pile dans le jeton.
  • si la liste est vide,
    • si i==i_0 alors tout est remonté à l'initiateur, il peut proclamer, finir, etc.
    • sinon P_i remonte le jeton de “meilleure remontée” à son voisin demandeur, c'est à dire son prédécesseur dans la pile.

Bonne question : à prime abord, 2(n-1) rien que pour le sondage (premier tour), car une étoile est un arbre couvrant et il faudrait un message vers puis un message de chaque satellite (n-1).

En cours, nous avons ensuite traité ce problème en deux temps: d'abord en supposant que l'initiateur (P_{i_0}) est la racine, puis en apportant des modifications pour passer au cas général.

• initiateur est P_{i_0}
• FIFO, arbre
• N = nombre de sites dans le reseau/graphe, et c'est connu de tous

• Si P_{i_0} n'a pas de fils, il répond FIN; sinon, il envoie REQ à tous ses fils.
• un noeud qui reçoit REQ propage à ses fils s'il en a; sinon, il renvoie REP (avec sa capacité et ID) au père
• lorsqu'un noeud a les réponses de tous ses fils, il remonte REP au père avec la meilleur réponse
• Lorsque P_{i_0} a toutes les réponses, il connait la meilleur capacité et “chez qui” et proclame.

• INIT : Si P_{i_0} n'a pas de fils, il répond FIN; sinon, il envoie REQ à tous ses fils
• RECEPTION :
  • Lorsque P_i reçoit REQ, il initialise un tableau de meilleur résultat: bestcap = c_i, bestid= i;
    • si P_i a des fils, P_i envoie REQ à tous ses fils
    • sinon P_i envoie REP(bestcap, bestid) à son père.
  • Lorsque P_i reçoit REP(c,id)
    • si c>bestcap alors {bestcap:=c ; bestid := id}
    • sinon NOP
    • s'il a reçu une réponse de tous ses fils, alors
      • si P_i est l'initiateur (P_{i_0}) : Proclamation
      • sinon P_i envoie REP (bestcap, bestid) à son père.

• lorsque P_i reçoit REQ de P_j,
  • il note, en fonction de REQ et de sa propre capacité:
    1. bestcap := c
    2. bestid := i
    3. DEM := P_j
    4. REQ_ID := P_{i_0} /pour reconnaitre cet élection parmi d'autres/
  • si P_i connait d'autres sites que P_j (ses “proches” au lieu de voisins) P_i envoie REQ à tous ces sites et note N_req, le nombre de ces REQ.
    • autrement dit,
      1. N_{Req} := le nombre de ses proches (fils et père)
      2. si N_{Req} \gt 1 (il a d'autres proches que DEM) P_{i} envoie REQ(bestcap, bestid, REQ_ID) à tous ses proches sauf P_j [“DEM”].
  • sinon il envoie REP(bestcap, bestid, REQ_ID) à P_j
• lorsque P_i reçoit REP(c,id) de P_j
  • il diminue N_req (en supposant que aucun site ne peut répondre plus d'une fois)
  • si c > bestcap…
  • si il a reçu une réponse de tous ses sites (N_req==0)
    • si P_i == P_{i_0} : Proclamation
    • sinon, P_i envoie REP(bestcap, bestid, REQ_ID) à DEM

Les principales différences entre “la” solution et ma proposition sont:

• “la” solution utilise deux types de messages, au lieu de demander à chaque site de deviner la nature du message en fonction da sa présence/absence dans une liste de sites “ayant vu” portée par le message.
• “la solution” crée le tableau “bestrep” de suite, tandis que mon protocol attendait la première réponse
• “la solution” n'accumule pas l'information (le chemin) permettant d'envoyer une tache de l'initiateur au gagnant une fois l'élection terminé