Paxos

paxos-simple-Copy.pdf (microsoft.com)

Problem

• Choosing a single value among all
• Proposers, Acceptors, Learners

Choosing a Value

• P1. An acceptor must accept the first proposal
  • (Because what if there is only a single proposal)
• imply => Acceptors must be allowed to accept more
  • (If not, what if no majority?)
  • However, need to ensure all chosen proposals have the same value =>
  • => introduce proposal number
  • A value is chosen when a single proposal with that value has been accepted by a majority of the acceptors.
• P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.
  • Can be satisfied by
• P2a . If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.
  • Can be satisfied by
• P2b . If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.
  • Can be satisfied by
• P2c . For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either ^9e1ee4
  • (a) no acceptor in S has accepted any proposal numbered less than n, or ^42ee99
  • (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S. ^4130fe
• => Proposer need to highest-number proposal less than $n$
• => Can’t predict future => request promise

The Algorithm

1. Proposer choose a proposal number $n$ and send prepare request to acceptors
2. Acceptors response with
   1. Promise: never accept a proposal less than $n$, and
   2. The proposal with highest number less than n that accepted
3. If proposer receives responses from majority
   1. issue proposal with number $n$ and $v$, where $v$ is the highest-number proposal
   2. if no proposals => any $v$
4. Send accept requests to acceptors
5. Acceptors accept iff it has not responded to a prepare request greater than $n$

Client Store

• Highest numbered prepare request
• Highest numbered it has ever accepted

Learners

• Acceptors send accepted value to a set of learners
• Learners inform other learners

Multipaxos

• Solve Replicated State Machines
• Optimization
  • Select Leader (highest id)
  • Prepare for the entire log, eliminate most prepare
  • Return noMoreAccepted if no accepted for log after current (OK in paper)
  • (Proposer skip prepare if every accepter noMoreAccepted)
• Example
  • Leader: 1-134, 138, 139
  • Phase 1 for 135-137, 140-
  • Leader run Paxos, find out 135, 140
  • Servers execute 1-135
  • Leader fill 136, 137 with noop
  • Servers execute 138-140
• Add/removing servers
  • Use log to manage changes

Appendix

P2c Prove

• Suppose some proposal with number $m$ and value $v$ is chosen
• And suppose P2c[[#^9e1ee4]] (Proposer only propose (v, n) if (a) or (b))
• Prove any proposal issued with number $n>m$ also has value $v$
• Induction hypothesis: Suppose every proposal issued with a number in $m$…($n$ − 1) has value $v$
• Base Case
  • The statement hold when $n=m$
• Inductive step
  • *Suppose every proposal issued with a number in $m$…($n$ − 1) has value $v$
  • => Every acceptor in some majority set $C$ accepted $v$
  • => Every acceptor in C has accepted a proposal with number in $m$…$(n-1)$
  • Because at least each of them has accepted a proposal with number $m$
  • => Every proposal with number in $m$…$(n-1)$ accepted by any acceptor has value $v$
  • By following P2c, the next proposal $n$ will have value $v$
  • P2c(a) [[#^42ee99]] will not happen because a majority set $C$ accepted $v$
  • P2c(b) [[#^4130fe]] come into play and will propose $v$
  • If $n=k-1$ holds, then $n=k$ holds
  • If $n=k-1$ holds - => any proposal issued with number $n>m$ also has value $v$
    ds.algorithms - Paxos made simple, invariant P2c - Theoretical Computer Science Stack Exchange
    Paxos lecture (Raft user study) - YouTube

In class

Focus on input to Replicated State Machines

• Paxos
  • High overheads
  • Better for small amount of essential info
• Chain
  • Used to agree on membership replication
• Basic
  • single value
• Multi Paxos
  • no clear definition

Single paxos

Components

• Proposers
• Acceptors
  • Store chosen value
  • Know chosen value (learner)
• Clients talk to proposers

Broken implementation

1. Single acceptor
   • single point of failure
2. => Multiple acceptors & accept only first value
   • Work if one fail
   • Fail if more than 2 proposers => might not be majority
3. => Accept every value
   • Might accept multiple values => bad
4. => Need to discover previous proposal
   • Still might accept multiple values
   • ![[attachments/Paxos Bad.png]]
5. => Must order proposals, reject old ones

Basic Paxos

• Proposal Numbers
  • Each proposal has a unique number
    • Higher numbers take priority
  • Simple approach
    • |round number|server id|
    • Every server stores maxRound (largest round number it has seen so far)
• Two-phase approach
  • Phase 1 Prepare
    • Find out any chosen value
    • Block older proposals that have not yet completed
    • (acceptors promise not to accept older proposals)
  • Phase 2 Accept
    • Ask acceptors to accept a specific value
• No Liveness guarantee
  • Solution 1: Randomize delay before restarting
  • Solution 2: Leader election (Multi paxos)