ALGOREP: Consensus is possible ! Paxos

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
  $\text{color}redred$
• P3, P4 accepts
  $\text{color}blueblue$
• P5 accepts
  $\text{color}greengreen$

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

1. On va envoyer des messages Prepare
   • "Je vais bloquer toutes les anciennes propositions"
2. Broadcast accept
   • "J'accepte ta valeur"

Conceptual Roles in Paxos

• Proposer
• Acceptors
• Learners: learn the outcome

Overview

Phase 1

1. $[Proposer]$ Choose a proposal number
   $n$
2. $[Proposer]$ Broadcast prepare(n) to all servers
3. $[Acceptor]$ Response to prepare(n)
   • if
     $n>minProposal$ then
     $minProposal=n$
   • Return (accepted_proposal, accepted_value)
4. $[Proposer]$ When responses received from majority
   • if any accepted_value returned, replace value by accepted value for highest accepted_proposal

Phase 2

1. $[Proposer]$ Broadcast accept(n, value) to all servers
2. $[Acceptor]$ Response to accept(n, value)
   • if
     $n\ge minProposal$ then accepted proposal = min proposal = n, accepted value = value
   • Return (min proposal)
3. $[Proposer]$ When responses received from majority
   • Any objection
     $(result>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