SDR

Diffusion

Olivier Lemer

Élection avec pannes

Rappels

Chang et Roberts, 1979

L'initiateur envoie son aptitude et son id.

Nouvelle aptitude

A

5

B

E

C

D

4

7

2

A-5

En élection

Connait l'élu

Chang et Roberts, 1979

L'initiateur 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

7

2

En élection

Connait l'élu

A-5

"A est plus apte que moi..."

Chang et Roberts, 1979

L'initiateur 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

7

2

En élection

Connait l'élu

A-5

"A est plus apte que moi..."

Chang et Roberts, 1979

L'initiateur 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

7

2

En élection

Connait l'élu

D-7

"Je suis plus apte que A!"

Chang et Roberts, 1979

L'initiateur 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

7

2

En élection

Connait l'élu

"D est plus apte que moi..."

D-7

Chang et Roberts, 1979

L'initiateur 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

7

2

En élection

Connait l'élu

D-7

"D est plus apte que moi..."

Chang et Roberts, 1979

L'initiateur 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

L'annonce a fait le tour, je suis élu !

d'un autre

Je propage le résultat

A

5

B

E

C

D

4

7

2

En élection

Connait l'élu

"C'est mon annonce, je suis élu !"

D-7

Chang et Roberts, 1979

L'initiateur 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

L'annonce 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

7

2

En élection

Connait l'élu

D-7

"Ah, c'est D qui a gagné !"

Chang et Roberts, 1979

L'initiateur 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

L'annonce 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

7

2

En élection

Connait l'élu

D-7

"Tout le monde sait, c'est officiel !"

Tour de résultat

Chang et Roberts, 1979

L'initiateur 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

L'annonce 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

7

2

En élection

Connait l'élu

Est l'élu

Tour de résultat

Maintien de l'anneau

Pour séparer les préoccupations

Separation of concerns

Chang et Roberts

Maintenance d'un anneau

"Envoie ça au suivant"

"On a reçu ça du précédent"

Maintenir un anneau

Validité : si un processus correct envoie m, alors m est délivré par le premier processus qui le suit dans l'anneau et n'est pas en panne.

Intégrité : m est délivré au plus une fois, seulement s'il a été envoyé, et dans l'ordre d'envoi.

Maintenance d'un anneau

"Envoie ça au suivant"

"On a reçu ça du précédent"

Suppositions

Pas de perte de messages.
Pas de duplication de messages.
Pas de changement d'ordre de messages.

Une panne peut être récupérable.
Au moins 2 processus corrects.

Durée de transit maximale bornée par une constante T.
Durées de traitement négligeables.

Chaque processus connait tous les autres.

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

Exemple

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

Résumé

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

Délivrer m à la couche applicative

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 ?

Validité ?

Si un processus correct envoie m, alors m est délivré par le premier processus qui le suit dans l'anneau et n'est pas en panne.

Propriétés

Oui

Validité ?

Intégrité ?

Oui

Non

Intégrité ?

m est délivré au plus une fois, seulement s'il a été envoyé, et dans l'ordre d'envoi.

Un processus lent peut être sauté à tort : il délivre le message, et son suivant aussi.

Avec anneau maintenu

Chang et Roberts avec gestion de pannes

Separation of concerns

Chang et Roberts

Maintenance d'un anneau

"Envoie ça au suivant"

"On a reçu ça du précédent"

Changements nécessaires

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

5

2

En élection

Connait l'élu

Est l'élu

A-4

Risque de famine

A

B

E

C

D

4

7

5

2

En élection

Connait l'élu

Est l'élu

B-7

(Ignorons les ACKs pour la lisibilité)

Risque de famine

A

B

E

C

D

4

7

5

2

En élection

Connait l'élu

Est l'élu

B-7

Risque de famine

A

B

E

C

D

4

7

5

2

En élection

Connait l'élu

Est l'élu

B-7

Risque de famine

A

B

E

C

D

4

7

5

2

En élection

Connait l'élu

Est l'élu

B-7

timeout !

Risque de famine

A

B

E

C

D

4

7

5

2

En élection

Connait l'élu

Est l'élu

B-7

La phase "annonce" se termine quand l'élu reçoit son annonce.

Ça n'arrivera jamais...

B-7

Risque de famine

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 :

id du processus à la meilleure aptitude jusqu'ici
meilleure aptitude jusqu'ici

Pour chaque processus traversé :

Après :

id du processus
aptitude du processus

{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

Changements nécessaires

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 :

id de l'élu

id de l'élu

Après :

id du processus

{i}

{

i_elu,

[i, j, ...]

}

Pour chaque processus visité

"Tous les processus ayant accepté le résultat."

Changements nécessaires

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 démarrera 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 démarrera une élection.

Chang et Roberts, 1979

Autres questions

Résumé

Avec anneau maintenu

Résumé

J'adopte la nouvelle aptitude

J'entre en élection

Changement d'aptitude

Réception d'une annonce

Si je ne suis pas en cours d'élection

Si je suis en cours d'élection

Je la mets de côté

(je l'adopterai en sortant d'élection)

J'envoie une annonce [{moi, apt}]

Si je suis dans la liste de l'annonce

Je calcule l'élu d'après la liste

J'envoie un résultat {élu, [moi]}

Je sors d'élection

Sinon

J'ajoute {moi, apt} dans la liste

J'envoie la liste au suivant

J'entre en élection

Conceptuellement Inchangé

Notez : Tout ça indépendamment de mon état (en élection ou non)

Réception d'un résultat

J'adopte la nouvelle aptitude

J'entre en élection

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

Je la mets de côté

(je l'adopterai en sortant d'élection)

J'envoie une annonce [{moi, apt}]

Si je suis dans la liste de l'annonce

Je calcule l'élu d'après la liste

J'envoie un résultat {élu, [moi]}

Je sors d'élection

Sinon

J'ajoute {moi, apt} dans la liste

J'envoie la liste au suivant

Si je suis dans la liste

Je n'ai rien à faire !

Si je ne suis pas dans la liste

J'entre en élection et j'envoie une annonce [{moi, apt}]

Sinon

Je note le nouvel élu

Je m'ajoute à la liste

J'envoie un résultat avec l'élu et cette liste

Je sors d'élection.

Pourquoi pas plus ?

Je suis dans la liste, tout le monde (pas en panne) a vu le résultat, on peut s'arrêter.

J'entre en élection

Si je ne suis pas en élection

et l'élu reçu est différent du mien

Changement d'aptitude

Résumé

Pseudocode

Avec anneau maintenu

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

apt_pending

entier, init ⊥

aptitude mise de côté

Pseudocode

Remarques

Plus besoin de l'id du prochain dans l'anneau : l'envoi est géré par le mainteneur d'anneau.

Démarrer une élection

Écouter infiniment les événements suivants :

Demande de changement d'aptitude à new_apt

Demande d'obtention de l'élu par la couche applicative

Réception d'une annonce de i avec liste participants

Réception d'un résultat de i avec {new_élu, accepted}

Note : les traitements de ces événements sont faits de manière séquentielle.

Initialisation

Pseudocode

Si inElection

apt_pending ← new_apt

Sinon

apt_self ← new_apt

Démarrer une élection

Demande de changement d'aptitude à new_apt

Inchangé

Retourner élu.

Demande d'obtention de l'élu

Inchangé

Pseudocode

Envoi d'une annonce [{self, apt_self}]

inElection ← true

Démarrer une élection

inElection ← false

Si apt_pending ≠ ⊥ et apt_pending ≠ apt_self

apt_self ← apt_pending

Démarrer une élection

apt_pending ← ⊥

Sortir d'élection

Pseudocode

Inchangé

Si self apparait dans participants

élu ← i tel que i a l'aptitude max dans participants

Envoi de résultat {élu, [self]}

Sortir d'élection

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)

Pseudocode

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

Démarrer une élection

Sinon

élu ← new_élu

Ajout de self dans accepted

Envoi d'un résultat {élu, accepted}

Sortir d'élection

(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)

Pseudocode

Exercice

On suppose 1s de transit pour chaque message

Cinq processus, formant un anneau dans le sens suivant

A, avec aptitude initiale de 2
B, avec aptitude initiale de 5
C, avec aptitude initiale de 1
D, avec aptitude initiale de 1
E, avec aptitude initiale de 7

Une première élection a déjà eu lieu : E est l'élu.

Les événements suivants ont lieu au bout d'une seconde :

L'aptitude de C devient 8, puis C tombe immédiatement en panne.
L'aptitude de D devient 2.

On suppose donc que les timeouts durent 2s

C8

A

2

B

C

D

E

D2

C8,D2

D2,E7

C8,D2,E7

D2,E7,A2

C8,D2,E7,A2

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,D

E

Exercice

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 changement d'aptitude ni panne, 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

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 à

l'acceptation d'une annonce que l'on a déjà acceptée alors qu'on n'est pas en élection, et
le mécanisme de lancement d'une nouvelle élection à la réception d'un résultat d'élection inattendu et inégal à son élu local ;

autrement dit, la gestion gracieuse de messages anormaux.