Olivier Lemer
Chang et Roberts, 1979
Le demandeur envoie son aptitude et son id.
Demande d'élection
A
5
B
E
C
D
4
3
7
2
A-5
En élection
Connait l'élu
Le demandeur envoie son aptitude et son id.
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
A-5
"A est plus apte que moi..."
Le demandeur envoie son aptitude et son id.
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
d'un autre
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
A-5
"A est plus apte que moi..."
Le demandeur envoie son aptitude et son id.
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
d'un autre
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
D-7
"Je suis plus apte que A!"
Le demandeur envoie son aptitude et son id.
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
d'un autre
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
"D est plus apte que moi..."
D-7
Le demandeur envoie son aptitude et son id.
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
d'un autre
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
D-7
"D est plus apte que moi..."
Le demandeur envoie son aptitude et son id.
Tour d'annonce
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
Si je reçois ma propre aptitude
La demande a fait le tour, je suis élu !
d'un autre
Je propage le résultat
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
"C'est ma requête, je suis élu !"
D-7
D-7
D-7
Le demandeur envoie son aptitude et son id.
Tour d'annonce
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
Si je reçois ma propre aptitude
La demande a fait le tour, je suis élu !
d'un autre
Je propage le résultat
Si je reçois un résultat
Je le propage
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
D-7
"Ah, c'est D qui a gagné !"
Le demandeur envoie son aptitude et son id.
Tour d'annonce
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
Si je reçois ma propre aptitude
La demande a fait le tour, je suis élu !
d'un autre
Je propage le résultat
Si je reçois un résultat
Je le propage si ce n'est pas le mien
Sinon, l'élection est finie, je suis l'élu
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
D-7
D-7
D-7
"Tout le monde sait, c'est officiel !"
Tour de résultat
Le demandeur envoie son aptitude et son id.
Tour d'annonce
Si je reçois une aptitude
Je la compare à la mienne
Je propage la plus grande des deux
Si je reçois ma propre aptitude
La demande a fait le tour, je suis élu !
d'un autre
Je propage le résultat
Si je reçois un résultat
Je le propage si ce n'est pas le mien
Sinon, l'élection est finie, je suis l'élu
A
5
B
E
C
D
4
3
7
2
En élection
Connait l'élu
Est l'élu
Tour de résultat
Pour séparer les préoccupations
Chang et Roberts
Maintenance d'un anneau
"Envoie ça au suivant"
"On a reçu ça du précédent"
Tout envoi doit être reçu par le prochain processus valide de l'anneau.
Toute réception doit venir du prédécesseur valide le plus proche sur l'anneau.
Maintenance d'un anneau
"Envoie ça au suivant"
"On a reçu ça du précédent"
T.
Lors d'une demande d'envoi,
envoie au prochain processus
lance un timeout
Lors d'une réception de message,
notifie la réception de ce message, et
A
B
C
envoie le message au prochain dans l'anneau.
envoie ACK avec un id du message.
Lors d'une réception de ACK,
annule le timer associé.
, et
qui, une fois écoulé :
"Envoie m1"
m1
"Reçu m1"
ACK,m1
"Envoie m2"
m2
ACK,m2
"Reçu m2"
m2
Incrémenter t
Réception de m et t_i
Réception de ACK avec t_i
Envoyer message et t au nième suivant dans l'anneau
Chaque processus a une estampille t.
Lancer un timer, dont le timeout
Demande l'envoi du message au (n+1)ième suivant.
Demande d'envoi au nième suivant
Notifier de la réception
Annuler le timeout associé à t_i
Répondre ACK avec t_i
(pour identifier les messages)
Et si on enlevait la supposition d'un délai max de transit ?
Complet ?
Si un processus tombe en panne, le message sera envoyé au suivant.
Oui
Oui
Complet ?
Correct ?
Correct un jour ?
Oui
Non
Non
Correct ?
Si un message est envoyé au n+1, alors le processus n était en panne.
Si un message est envoyé au n+1 à chaque fois, alors le processus n était en panne.
Chang et Roberts avec gestion de pannes
Chang et Roberts
Maintenance d'un anneau
"Envoie ça au suivant"
"On a reçu ça du précédent"
Pour gérer les pannes
Toutes communications à travers le mainteneur d'anneau.
C'est tout ?
Risque de famine !
A
B
E
C
D
4
7
3
5
2
En élection
Connait l'élu
Est l'élu
A-4
A
B
E
C
D
4
7
3
5
2
En élection
Connait l'élu
Est l'élu
B-7
(Ignorons les ACKs pour la lisibilité)
A
B
E
C
D
4
7
3
5
2
En élection
Connait l'élu
Est l'élu
B-7
B-7
A
B
E
C
D
4
7
3
5
2
En élection
Connait l'élu
Est l'élu
B-7
A
B
E
C
D
4
7
3
5
2
En élection
Connait l'élu
Est l'élu
B-7
timeout !
A
B
E
C
D
4
7
3
5
2
En élection
Connait l'élu
Est l'élu
B-7
B-7
B-7
La phase "annonce" se termine quand l'élu reçoit son annonce.
Ça n'arrivera jamais...
B-7
Comment ?
Transmettre avec l'annonce tous les processus visités jusqu'ici :
Quand je suis dans la liste d'une annonce : elle a fait le tour, j'élis le meilleur.
Satisfaits ?
Et si je rejoins une élection en cours ?
Avant :
Après :
{i, apt_i}
[
{i, apt_i},
{j, apt_j},
...
]
"Tous les processus ayant candidaté"
S'arrêter quand l'annonce a fait un tour complet
Idée
Pour gérer les pannes
Idée : Relancer l'élection si je n'y ai pas participé.
Comment ?
Transmettre avec le résultat tous les processus y ayant participé :
Si je reçois un résultat que je n'ai pas accepté et que je ne suis pas en élection, alors je n'y ai pas participé et je relance l'élection (sauf si mon élu est déjà le bon).
Et maintenant ?
Pas trop mal...
Avant :
Après :
{i}
{
i_elu,
[i, j, ...]
]
"Tous les processus ayant accepté le résultat."
Pour gérer les pannes
Si je reçois un résultat que j'ai accepté, il a fait le tour et je ne le propage pas.
Et si on enlevait la supposition qu'un transit dure moins de T unités de temps ?
On risque d'élire un processus dont l'aptitude n'est pas la plus grande.
Et si celui qui va être élu tombe en panne après l'envoi d'une annonce, mais réapparait avant la réception du résultat ?
Il sera élu ! Et personne ne l'aura remarqué !
Et si celui qui va être élu tombe en panne après l'envoi d'une annonce ?
Il sera élu ! C'est ensuite qu'un détecteur de panne le verra et relancera une élection.
Et si celui qui va être élu tombe en panne après l'envoi d'un résultat ?
Il sera élu ! C'est ensuite qu'un détecteur de panne le verra et relancera une élection.
Autres questions
Résumé
Demande d'élection par couche applicative
Réception d'une annonce
Si je ne suis pas en cours d'élection
Si je suis en cours d'élection
Si je suis dans la liste de l'annonce
Sinon
Conceptuellement Inchangé
Notez : Tout ça indépendamment de mon état (en élection ou non)
Réception d'un résultat
Réception d'une annonce
Réception d'un résultat
Si je ne suis pas en cours d'élection
Si je suis en cours d'élection
Si je suis dans la liste de l'annonce
Sinon
Si je suis dans la liste
Si je ne suis pas dans la liste
Pourquoi pas plus ?
Je suis dans la liste, tout le monde (pas en panne) a vu le résultat, on peut s'arrêter.
et l'élu reçu est différent du mien
Demande d'élection par couche applicative
Pseudocode
Variables
self
entier, constant
mon numéro de processus
inElection
booléen, init false
ssi une élection est en cours
élu
entier
id du processus élu
apt_self
entier
mon aptitude
Remarques
Plus besoin de l'id du prochain dans l'anneau : l'envoi est géré par le mainteneur d'anneau.
Écouter infiniment les événements suivants :
Demande d'élection
Demande d'obtention de l'élu par la couche applicative
Réception d'une annonce {i, apt_i}
Réception d'un résultat {i}
Note : les traitements de ces événements sont faits de manière séquentielle.
Initialisation
Si inElection
Refuser la demande
Sinon
Envoi d'une annonce [{self, apt_self}]
inElection ← true
Demande d'élection
Inchangé
Retourner élu.
Demande d'obtention de l'élu
Inchangé
Si self apparait dans participants
élu ← i tel que i a l'aptitude max dans participants
Envoi de résultat {élu, [self]}
inElection ← false
Sinon
Ajout de {self, apt_self} dans participants
Envoi d'annonce avec participants
inElection ← true
Réception d'une annonce de i avec liste participants
(L'annonce a fait le tour)
Si self n'apparait pas dans accepted
Réception d'un résultat de i avec {new_élu, accepted}
Si pas inElection et élu n'est pas new_élu
Envoi d'une annonce [{self, apt_self}]
inElection ← true
Sinon
élu ← new_élu
Ajout de self dans accepted
Envoi d'un résultat {élu, accepted}
inElection ← false
(Il s'agit d'un résultat inédit)
(Il s'agit d'une élection inédite)
(il faut recommencer)
(j'accepte le résultat)
On suppose 1s de transit pour chaque message
Cinq processus, formant un anneau dans le sens suivant
A, avec aptitude initiale de 2B, avec aptitude initiale de 5C, avec aptitude initiale de 8D, avec aptitude initiale de 2E, avec aptitude initiale de 7
Les événements suivants ont lieu au bout d'une seconde :
C demande une élection, puis tombe immédiatement en panne.D demande une élection.On suppose donc que les timeouts durent 2s
C8
A
2
B
5
C
8
D
2
E
7
D2
C8,D2
D2,E7
C8,D2,E7
D2,E7,A2
C8,D2,E7,A2
D2,E7,A2,B5
D2,E7,A2,B5
C8,D2,E7,A2,B5
E|D
C|D
C8,D2,E7,A2,B5
E|D,E
E7
E|D,E,A
E7,A2
E|D,E,A,B
E7,A2,B5
E|D,E,A,B
E7,A2,B5
E7,A2,B5,D2
E|E
E|E,A
E|E,A,B
E|E,A,B
E|E,A,B,D
E
E
E
E
C
E
L'algorithme décrit aujourd'hui offre-t-il une garantie d'élection de la plus haute aptitude un jour, ou immédiatement ?
Garantie d'élection de la plus haute aptitude...
... un jour :
Après une durée suffisamment grande sans demande d'élection, tous les processus corrects ont comme élu le processus à la plus haute aptitude.
... immédiatement :
Lorsqu'une élection se termine sur un processus p, celui-ci a comme élu le processus à la plus haute aptitude.
Si la garantie est immédiate, démontrez-le ;
Sinon, donnez-en un contre-exemple.
A
2
B
3
A2
B
B3
B3,A2
A2,B3
B|A
B|B
B
Nouvelle aptitude : 1
B1
B
B|A,B
B1,A2
A|B
A
B|B,A
B
A2
A2,B1
A
A|A
La garantie n'est que un jour.
Cela peut arriver lorsque le résultat d'une ancienne élection arrive durant une nouvelle élection.
Cependant, la garantie finit par être à nouveau respectée, grâce à
autrement dit, la gestion grâcieuse de messages anormaux.