Olivier Lemer
Qu'est-ce que c'est ?
A
B
C
D
E
Au début
Chaque processus propose une valeur.
"Je propose lundi en 8"
"Je propose demain"
"Je propose ce mardi"
"Je propose jamais"
"Je propose dans 10 ans"
Par exemple : quand est-ce qu'on se voit ?
Qu'est-ce que c'est ?
A
B
C
D
E
Processing...
Au début
Chaque processus propose une valeur.
Qu'est-ce que c'est ?
A
B
C
D
E
Au début
Chaque processus propose une valeur.
À la fin
Chaque processus décide la même valeur.
"Je décide
demain"
"Je décide
demain"
"Je décide
demain"
"Je décide
demain"
"Je décide
demain"
(Laquelle ? C'est sans importance)
Pas de perte, de duplication, ou de réordonancement des messages.
Toute panne est permanente.
Il existe une borne supérieure constante T sur la durée de transit de tout message.
On a donc un système "synchrone".
(À ne pas confondre avec un algorithme synchrone)
Les durées de traitement sont négligeables.
Le réseau est une clique (tous connectés à tous).
Comprendre : on pourra utiliser un détecteur de pannes parfait
"C'est une supposition irréaliste d'avoir une borne sur le transit de messages"
Et pourtant on l'utilise quand même ! Pourquoi ?
T ?"Sans garantie sur la durée de transit des messages, il est impossible d'atteindre un consensus,
Fischer, M., N. Lynch, and M. Paterson (1985).
dès que même un seul processus peut tomber en panne."
On a donc besoin d'un système au moins partiellement synchrone.
On fait ici une supposition plus forte (système synchrone) pour simplifier.
Ce qui définit le consensus
Terminaison
Tout processus correct décide d'une valeur, un jour.
(on finira par décider)
Validité
Si un processus décide v, alors un processus a proposé v.
(on n'invente pas de valeur)
Unicité
Aucun processus ne décide deux fois.
(une décision par consensus)
Accord
Tous deux processus décident la même valeur
(on décide tous pareil)
Quand je propose
Envoyer ma proposition à tout le monde.
Quand j'ai reçu toutes les propositions
J'en choisis une de manière déterministe.
A
B
C
D
Problème ?
Si un processus tombe en panne ?
(i.e. en suivant tous le même algorithme)
Quand je propose
Envoyer ma proposition à tout le monde.
Quand j'ai reçu toutes les propositions
J'en choisis une de manière déterministe.
A
B
C
D
Durant un envoi ?
"toujours rien reçu de D..."
"toujours rien reçu de D..."
Problème ?
Si un processus tombe en panne ?
Risque de perte de terminaison.
"tout reçu, je décide !"
Quand je propose
Envoyer ma proposition à tout le monde.
Quand j'ai reçu toutes les propositions
J'en choisis une de manière déterministe.
A
B
C
D
Durant un envoi ?
Problème ?
Si un processus tombe en panne ?
Risque de perte de terminaison,
"panne détectée !"
"panne détectée !"
"panne détectée !"
"Je n'attends plus D, je décide !"
ou d'accord (si détection de pannes).
"Je n'attends plus D, je décide !"
Le problème
Le problème
Si un processus tombe en panne
Possible que tout le monde n'ait pas toutes les valeurs.
A est seul à avoir reçu la valeur de D,
et a donc une vue différente des autres.
Reçu les propositions de :
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
Solution ?
Souvenez-vous de la propriété de "Validité" :
"Si un processus décide v, alors un processus a proposé v."
Tout processus, pas forcément correct !
Donc la proposition de D reste dans la course !
Si un processus tombe en panne
Possible que tout le monde n'ait pas toutes les valeurs.
Qu'est-ce qu'on veut ? On garde la proposition de D ou pas ?
Le problème
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
Solution ?
Quand je n'attends plus de proposition, je lance un nouveau round.
Si un processus tombe en panne
Possible que tout le monde n'ait pas toutes les valeurs.
Soit j'ai reçu la proposition, soit j'ai détecté une panne.
Le problème
Comme solution à notre problème
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
On est bon ?
"tout reçu !"
"tout reçu !"
"tout reçu !"
Si un processus tombe en panne
Je lance un deuxième round, avec toutes les valeurs connues.
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
Non ! Même problème !
Si un processus tombe en panne
Je lance un deuxième round, avec toutes les valeurs connues.
On est bon ?
[A,B,C,D]
[A,B,C]
"tout reçu !"
"tout reçu !"
"tout reçu !"
Seul B a reçu les données de A,
et donc celles de D.
C a encore une vision incomplète.
Solution ?
On refait pareil !
Quand j'ai reçu la proposition de chaque processus non détecté
Je lance un nouveau round, avec toutes les valeurs connues.
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
[A,B,C,D]
[A,B,C]
Et là, on est bon ?
Peut-être...
Une précision, d'abord...
[A,B,C,D]
[A,B,C,D]
Tous d'accord !
Détection en retard d'une panne
Quand j'ai reçu la proposition de chaque processus non détecté
Je lance un nouveau round, avec toutes les valeurs connues.
A
B
C
D
[A,B,C]
[A,B,C]
On a dit...
Donc dans notre exemple, A n'attend pas de détecter D !
A sera donc au round suivant quand il détectera la panne...
[A,B,C,D]
Non ! A n'attendra plus les messages de D, rien d'anormal.
Problème ?
Ou "quand s'arrêter" ?
Quand suis-je sûr d'avoir toutes les propositions ?
Je ne peux pas compter sur le détecteur de pannes, qui peut être en retard.
Comment, alors ?
Si je reçois de la part des mêmes processus deux fois de suite,
alors aucune panne n'a eu lieu entre temps.
Donc je suis sûr d'avoir toutes les propositions.
Est-ce que je peux m'arrêter, alors ?
Pas encore, je suis peut-être le seul dans cette situation.
Quand il n'y a pas eu de pannes pendant le round précédent.
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C]
[A,B,C,D]
[A,B,C]
B a une vision complète !
Que faire ?
Le dire à tout le monde !
(ici, il n'y a que C qui est encore en marche)
Round 1
A reçoit de B, C, D
B reçoit de A, C
C reçoit de A, B
Round 2
B reçoit de A, C
C reçoit de B
decide x
Jusqu'au "partage de décision"
Initialement
J'entre en round 1.
Ma liste de propositions ne contient que la mienne.
Quand j'entre en round x
J'envoie ma liste de propositions avec l'id de round.
Quand je reçois un message pour le round x
Si je ne suis pas encore en round x, je repousse sa réception.
Sinon, je mets à jour ma liste de propositions.
Quand j'ai reçu un message de tous ceux dont je n'ai pas détecté la panne
Si j'ai reçu, ce round, de la part des mêmes qu'au round précédent,
Je décide parmi mes propositions (de manière déterministe).
J'envoie ma décision à tous les processus en ligne, et je m'arrête.
Sinon,
Je passe au round suivant.
Quand j'ai reçu un message de tous ceux dont je n'ai pas détecté la panne
Si j'ai reçu, ce round, de la part des mêmes qu'au round précédent,
Je décide parmi mes propositions (de manière déterministe).
Quand je reçois une décision
Je note et je m'arrête ?
Non ! Même risque qu'avant
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
J'envoie ma décision à tous les processus en ligne, et je m'arrête.
Quand j'ai reçu un message de tous ceux dont je n'ai pas détecté la panne
Si j'ai reçu, ce round, de la part des mêmes qu'au round précédent,
Je décide parmi mes propositions (de manière déterministe).
Quand je reçois une décision
Je note et je m'arrête ?
Non ! Même risque qu'avant
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
"Je note et je m'arrête"
"Qu'est-ce qui se passe ?"
J'envoie ma décision à tous les processus en ligne, et je m'arrête.
Quand j'ai reçu un message de tous ceux dont je n'ai pas détecté la panne
Si j'ai reçu, ce round, de la part des mêmes qu'au round précédent,
Je décide parmi mes propositions (de manière déterministe).
J'envoie ma décision à tous les processus en ligne, et je m'arrête.
Quand je reçois une décision
Je propage, et je m'arrête.
A
B
C
D
[A,B,C,D]
[A,B,C]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
"Je propage et je m'arrête"
"Je propage et je m'arrête"
Remarque
L'approche utilisée ici,
A
B
C
D
"Je propage et je m'arrête"
"Je propage et je m'arrête"
"À la réception d'un broadcast, je broadcast à mon tour"
n'est pas spécifique au consensus.
On l'utilise dès qu'une panne peut arriver pendant un broadcast.
[A,B,C,D]
[A,B,C]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
[A,B,C,D]
et analyse de tolérance aux pannes
Quand je reçois une décision
Je propage, et je m'arrête.
Initialement
J'entre en round 1.
Ma liste ne contient que ma proposition.
Quand j'entre en round x
J'envoie ma liste de propositions avec l'id de round.
Quand je reçois un message pour le round x
Si je ne suis pas encore en round x, je repousse sa réception.
Sinon, je mets à jour ma liste de propositions.
Quand j'ai reçu un message de tous ceux dont je n'ai pas détecté la panne
Si j'ai reçu, ce round, de la part des mêmes qu'au round précédent,
Je décide parmi mes propositions (de manière déterministe).
J'envoie ma décision à tous les processus en ligne, et je m'arrête.
Sinon,
Je passe au round suivant.
Combien de pannes puis-je tolérer ?
Jusqu'à N-1 (!)
C'est excellent. En général, difficile de tolérer plus qu'une constante, ou N/2-1.
Un problème central
Tout type d'information peut être proposé
"Qui de nous sera l'élu ?"
"Qui de nous aura la SC ?"
Voire même
"Quelle modification fait-on ensuite de l'état global"
"Quelle transition applique-t-on sur une machine d'état partagée"
Ou de manière plus abstraite
Tous les processus maintiennent une copie de la même machine d'état :
Des états
Des transitions entre états
A
B
C
D
(par exemple, un ensemble de comptes bancaires)
(par exemple, des commandes pay)
pay 10
pay 3
pay 3
pay 5
pay 3
Si je souhaite modifier l'état, je lance un consensus et propose la modification
Tant que ma proposition n'a pas été acceptée, je recommence.
Consensus
pay 10
pay 10
pay 10
pay 10
pay 10
pay 3
pay 5
Consensus
pay 5
pay 5
pay 5
pay 5
pay 3
pay 3
pay 3
pay 3
Consensus
États
Graphe de dettes
Transitions
Ajouts de payements
Qui a le jeton de la SC
Passation du jeton à un autre
Qui est l'élu
Passation du rôle à un autre
Comptes en banque
Transaction d'un compte à un autre
Exemples
La solution à tout ?
Tout ce qui peut être modélisé par une machine d'état, donc oui.
Mais, bien plus lourd.
Encore lui, bien sûr
Diego Ongaro and John Ousterhou (2014)
Améliorations de Paxos
Suppositions
Jusqu'à N/2 pannes récupérables
Pas de panne arbitraire
Système partiellement asynchrone
Sur les messages : intégrité uniquement
Proposer une implémentation de l'exclusion mutuelle utilisant une abstraction de consensus (sous forme de boite noire).
Garantissez notamment
Nous souhaitons avoir un algorithme de consensus permettant de s'accorder non plus sur une proposition, mais sur une liste de propositions, contenant toutes les propositions des processus valides, et autorisant les propositions de processus en panne.
Comment un tel algorithme pourrait-il être utilisé dans votre projet ChatsApp, afin d'offrir la garantie d'ordre global de réception des messages ?
Proposer une première version supposant un réseau synchrone.
Proposer ensuite une version ne faisant pas de supposition sur le réseau, utilisant (sous forme de boite noire) un algorithme de consensus tolérant un réseau asynchrone.
Des consensus sont lancés en boucle.
À chaque instance de consensus, je partage ma demande si j'en ai une, ainsi que le TS associé.
La fonction de décision déterministe sélectionne la proposition dont le TS est le plus ancien.
Aussi, un processus en cours de SC doit attendre la fin de sa SC avant de faire sa proposition au prochain consensus. Sinon, il serait possible d'avoir plusieurs processus en SC en même temps.
La solution simple est de modifier le consensus vu en cours pour qu'il retourne la liste des propositions au moment de la décision, sans en sélectionner une arbitrairement.
En utilisant un consensus comme boite noire, on doit
Si notre proposition n'apparait pas dans le résultat du consensus, c'est que notre message n'avait pas eu le temps d'arriver ; on relance donc un consensus avec une liste de toutes les propositions reçues jusqu'ici, la nôtre incluse.
Avec un tel algorithme, on pourrait ne plus utiliser de mutex. À la place, on aurait des consensus en boucle. À chaque nouvelle instance de consensus, on lui passe les messages qu'on aimerait broadcast, puis on attend le résultat du consensus, qui sera les messages à afficher ainsi que leur ordre. Si nos messages n'y apparaissent pas tous, on les proposera à nouveau au prochain consensus.