Lien de la note Hackmd
A Word on Paxos
“On va abandonner les systemes distribues c’est trop chiant” Lamport: a prouve accidentellement que ca marche
Est-ce que Paxos c’est dur ?
Ca depend des gens
On veut arriver au consensus mais pas gagner
Comme si tous les candidats a la presidentielle veulent que quelqu’un soit elu
Intuition
On veut aller manger, tout le monde a faim et on a pas de chef. On peut discuter que un a un.
Des gens ont une idee initiale et des gens vont suivre
Qu’est-ce qu’il peut arriver ?
Soit aucune idee n’est acceptee Soit on arrive pas a avoir une majorite (“Tu veux manger quoi ?” “M’en fou”)
Problem: Split votes
Consider 5 processes:
- P1, P2 accepts $\color{red}{red}$
- P3, P4 accepts $\color{blue}{blue}$
- P5 accepts $\color{green}{green}$
Comment on fait ?
P5 rejoint un des groupes et tout le monde rejoint la majorite ? Comment P5 connait l’etat des autres ?
On va les faire fight en 1v1 gare du nord
On a rouge et noir On va envoyer un message a tous Avec le delai de propagation des messages, on va dire oui a noir ou oui a rouge Si noir arrive en premier, noir sera choisi, sinon rouge le sera Si on a propose noir et qu’on dit oui a rouge, alors on transmet le message comme quoi on propose rouge maintenant
Example
Paxos
Basic Paxos
2 phases
- On va envoyer des messages
Prepare- “Je vais bloquer toutes les anciennes propositions”
Broadcast accept- “J’accepte ta valeur”
Conceptual Roles in Paxos
- Proposer
- Acceptors
- Learners: learn the outcome
Overview
Phase 1
- $[Proposer]$ Choose a proposal number $n$
- $[Proposer]$ Broadcast
prepare(n)to all servers - $[Acceptor]$ Response to
prepare(n)- if $n\gt minProposal$ then $minProposal=n$
- Return (accepted_proposal, accepted_value)
- $[Proposer]$ When responses received from majority
- if any accepted_value returned, replace value by accepted value for highest accepted_proposal
Phase 2
- $[Proposer]$ Broadcast
accept(n, value)to all servers - $[Acceptor]$ Response to accept(n, value)
- if $n \ge minProposal$ then accepted proposal = min proposal = n, accepted value = value
- Return (min proposal)
- $[Proposer]$ When responses received from majority
- Any objection $(result \gt n)$ ? restart
- Otherwise, value is chosen
Example 2
Example 3
Liveness
Competing processes can livelock !
Les processus se battent pour avoir le dernier de la majorite
Solutions
Randomized delays before restarting
Multi-Paxos
Create a replicated log