Distributed System

Paper Digest - Paxos Made Simple

Paper digest - Paxos Made Simple

Motivation

  • Solve consensus problem on a single value (basic Paxos).
  • Consensus problem for a series of values that forming a log is solved using Multi-Paxos.

Consensus Problem

  • A consensus algorithm ensures that a single one among the proposed value is choose.
  • Chosen: meaning a consensus has been reached.
  • Safety properties of consensus:
    • Only a value that has been proposed may be chosen.
    • Only a single value can be chosen.
    • A process never learns that a value has been chosen unless it actually has been.
  • Liveness properties of consensus:
    • One of many proposed values is eventually chosen.
    • If a value is chosen, processes eventually learn about it.

Failure Models

  • Fail Stop: servers may crash, and stop forever.
  • Fail Recovery: servers may crash, but finally will restart and recover.
  • No Byzantine failures: messages can be delayed but they can’t be corrupted; servers can fail but they can’t behave maliciously.

Terms

  • Proposer: propose value. A proposer propose value by sending a proposal, which contains the value (among other things), to acceptors.
  • Acceptor: accept value proposed by proposer. Accept means acknowledge to proposer that the proposed value is accepted, by sending response to proposer.
  • Chosen: a value is chosen when majority of acceptors accept the value.
  • A process can be both a proposer and an acceptor.

Choose a Value

  • Single acceptor:
    • Easiest and most intuitive approach :)
    • However, it is not fault tolerant. If the single acceptor crashes, the system will not be able to make progress.
  • Multiple acceptors:
    • Solve the SPOF problem for single acceptor case.
    • A value is chosen when this value is accepted by a majority of acceptors.
    • This majority of acceptors is called a quorum.
    • Why majority? We need ensure that any two sets of quorum overlap. With drawer principle, if a quorum is majority, then any two majorities will have at least one acceptor in common.
    • Now why we need ensure any two sets of quorum overlap? This is for fault tolerance / recovery purpose - so that we can have at least one acceptor that has complete history of the states (of the Paxos state machine.)
    • Now why we need complete history? We need this so only a single value is chosen (important safety property). Why? Elaboration next.
  • How to choose a value
    • Case 1: single proposed value - only a single value is proposed from proposers.
      • If there is only a single value proposed ever, then this value has to be chosen.
      • This implies that an acceptor must accept the first proposal that it receives.
      • Conclusion: An acceptor must accept the first proposal that it receives. [P1]
    • Case 2: multiple proposed value - multiple values are proposed from proposers.
      • This raises a problem. With multiple proposed value, it is possible no single value is accepted by the quorum. So it’s possible consensus will never be reached, without additional constraints.
        • A sample case that consensus never reached:
          • 2 processes P1 and P2. P1 proposes V1 and P2 proposes V2.
          • V1 is accepted by P1 (or P2), V2 is accepted by P2 (or P1), because an acceptor must accept the first value it receives.
          • No proposal would ever get majority in such case.
      • To address the problem, where P1 must be true and yet a consensus has to be reached somehow, one additional constraint should be added:
        • An acceptor must be allowed to accept more than one proposal.
        • Since there are multiple proposals now, there is a need to distinguish between different proposals. The mechanism that serves this purpose is to use proposal number
        • A proposal number is a number attach to each proposal. How this is implemented depends on actual implementation.
      • With the new constraint that an accept can accept more than one proposal, there is a new problem: we may end up with multiple values chosen; this violates the safety property.
        • A sample case multiple values are chosen:
          • 5 processes, P1 through P5.
          • P1 proposes V1, P5 proposes V5.
          • V1 is accepted by P1, P2, and P3.
          • Assume there is a delay, and then V5 arrives to acceptor P3.
          • Since an acceptor can accept multiple values, P3 is happily accepting V5.
          • Meanwhile, V5 is accepted by P4, and P5. (It could also be accepted by P1 and P2 of course.)
          • The end result is no consensus reached: V1 and V5 are both gaining a majority.
        • To satisfy safety property of only a single value is chosen, an additional constraint should be added.
      • If a proposal with value v is chosen, then every higher numbered proposal that is chosen has value v. [P2]
        • Because proposals are ordered (use a proposal number), this ensures only a single value is chosen.
        • To be chosen a proposal must be accepted by at least one acceptor. So, we can satisfy P2 by satisfying:
        • If a proposal with value v is chosen, then every higher numbered proposal accepted by any acceptor has value v.
      • Constraint of P2 introduces a new problem that requires a strengthened constraint:
        • Now assume a value V is chosen already. Because chosen a value only requires a majority of acceptors, it is possible that the proposal WRT the chosen value never reached one or more acceptors.
        • Because an acceptor can be a proposer, from one of those unreached acceptors, one acceptor (now a proposer) may propose a new value with a higher proposal number.
        • Because of P1, an acceptor must accept the first proposal it receives. So an acceptor that receives this new proposal which contains a different value than the chosen value must be accepted.
        • This violates P2a, so we need add more constraints.
      • Maintaining both P1 and P2a requires strengthening P2a to P2b: If a proposal with value v is chosen, then every higher numbered proposal issued by any proposer has value v.
        • This means before a proposer proposes a value, it has to look around and see if there is any exiting chosen value.
        • But how to satisfy this new constraint P2b?
      • We can satisfy P2b by maintaining invariance of 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 (a) no acceptor in S has accepted any proposal numbered less
        than n, or (b) v is the value of the highest-numbered proposal among
        all proposals numbered less than n accepted by the acceptors in S. [P2c]
      • To satisfy P2c, now comes to my favorite part of the paper:
        • To maintain the invariance of P2c
          , a proposer that wants to issue a proposal
          numbered n must learn the highest-numbered proposal with number
          less than n, if any, that has been or will be accepted by each acceptor in
          some majority of acceptors. Learning about proposals already accepted is
          easy enough; predicting future acceptances is hard. Instead of trying to predict
          the future, the proposer controls it by extracting a promise that there
          won’t be any such acceptances. In other words, the proposer requests that
          the acceptors not accept any more proposals numbered less than n.

Proposer Algorithm

  • Two phases: prepare and propose.
  • Prepare: A proposer chooses a new proposal number n and sends a request to each member of some set of acceptors, asking it to respond with:
    • a. A promise never again to accept a proposal numbered less than n, and
    • b. The proposal with the highest number less than n that it has accepted, if any.
  • Propose: If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the highest-numbered proposal among the responses, or is any value selected by the proposer if the responders reported no proposals.

Acceptor Algorithm

  • An acceptor can ignore any request without compromising safety.
  • We need to say only when it is allowed to respond to a request.
  • It can always respond to a prepare request.
  • It can respond to an accept request, accepting the proposal, iff it has not promised not to.
  • Optimization: acceptor can ignore prepare requests which have lower proposal number, and also proposals that it already accepted.

Learning a Chosen Value

  • Use distinguished learners to optimize from product of number of learners and acceptors, to the sum of number of acceptors and learners.

Implementation

  • Single Paxos not so useful, as it only reaches consensus on a single value.
  • Multiple instances of Paxos - called multi-paxos allows consensus on a set of values. Very useful for building RSM (replicated state machine) systems.