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)