Written by Rui F. David
on 

Distributed Protocols

Paxos

Introduction

Paxos is a distributed consensus algorithm that allows several computers to agree on a single value. There are some variations of Paxos, as well as different implementations. We will see how Cassandra implemented Cassandra and what was changed from the original proposal [1].

There is a great essay from Leslie Lamport named “Paxos Made Simple” [2] which explains how the algorithm operates in two phases. Don’t worry about understanding it now, we will have some background before and come back to these phases.

Phase 1. (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) 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 2. (a) 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 wit 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.

(b) 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.

The three PALs: Proposers, Acceptors, and Learners

We start by describing the three roles in Paxos: Proposers, Acceptors, and Learners. A single process may have more than one role. In simple words, we can describe in a very high level:

Proposers: suggest a value for the group to agree on
Acceptors: vote on the proposed values
Learners: apply the values that was chosen

Phases

large Figure 1: Paxos Protocol.

Coming back to Lamport’s explanation [2], in the first phase a proposer picks proposal n and sends a Prepare(a) message to a majority of acceptors. nmust be unique across all proposers and greater than any number this proposer has used before.

References

  1. [1]L. Lamport, “The Part-Time Parliament,” ACM Transactions on Computer Systems, vol. 16, no. 2, pp. 133–169, May 1998, doi: 10.1145/279227.279229.
  2. [2]L. Lamport, “Paxos Made Simple,” ACM SIGACT News, vol. 32, no. 4, pp. 51–58, Dec. 2001, [Online]. Available at: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf.