Paxos is a Consensus algorithm for distributed systems. Paxos-Made-Simple is a great reference, if you want to understand Paxos without getting into mathematical nitty-gritty.

Requirements

In order to reach a consensus in the distributed environment, consensus should meet following requirements

  1. Only proposed value can be chosen.
  2. Only a single value is chosen.
  3. Process learns a value has been chosen only after it has actually been chosen.

Choosing a Value

  • Actors
    1. Proposer : Node suggesting value to other nodes.
    2. acceptor : Node receiving and accepting/rejecting value sent by proposer.
  • Request Types
    1. prepare request : request with seq n sent by proposer asking acceptor to never again accept a proposal less then n and also respond with accepted proposal < n.
    2. accept request : based on the majority response for the prepare request, proposer sends request with n and value to acceptors to accept.
  • Phase I
    1. Proposer selects a proposal number n and sends prepare request with number n to a majority of acceptors.
    2. If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
  • Phase II
    1. If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
    2. If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

Learning a Chosen Value

More reliable and less chatty way to inform learners about proposal is by designating some learners to act as distinguished learners. acceptors can inform distinguished learners about decision and distinguished learners can in turn inform other learners about this decision. This flow is possible because of non-Byzantine(message can not be corrupted) model.