Election sur un anneau unidirectionnel
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 :
Calcul | processus
de calcul
pour
son appli. | démons:
election
excl.mut
etc. | Contrôle |
| opérations locales | |
| “natif” | |
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 :
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
GC
1) unidirectionnel FIFO
P_{i_0} est le site initiateur
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).
chaque machine change ces deux derniers éléments si sa capacité est supérieur, et transmet le jeton à son successeur.
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.
Premier tour (sondage) | n |
2° tour (proclamation) | n |
Total | 2N |
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é.
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”
le site initiateur envoie un
jeton message de sondage à chacun de ses voisins
2), 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.
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} ]:
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.
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.
lorsque P_i reçoit REQ de P_j,
il note, en fonction de REQ et de sa propre capacité:
bestcap := c
bestid := i
DEM := P_j
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,
N_{Req} := le nombre de ses proches (fils et père)
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
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é