Review of "Paxos Made Simple"

Paxos algorithm is widely used in fault tolerant distributed systems, but has been regarded as difficult to understand. This paper makes it much easier for readers to understand the Paxos algorithm and different guarantees.

A consensus algorithm guarantees safety of values committed to the system, more specifically, 1) only a value that has been proposed may be chosen, 2) only a single value is chosen, and 3) a process never learns that a value has been chosen unless it has been. There are three types of agents in a Paxos algorithm runtime. proposers, acceptors, and learners. In an implementation, a single process may act as more than one agent.

Paxos uses two phases to propose and accept a value. In the prepare phase, a proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors. When an acceptor receives this request with number n greater than that of any prepare request to which it has already responded, it responds 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. In the second phase – accept phase, the proposer receives the responses to its prepare requests 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. If acceptor receives an accept request for a proposal numbered n, it accepts it unless it has responded to a prepare request having a number greater than n.

Will this paper be influential in 10 years? Yes, I think so, it has been for over a decade now and a lot of systems are using it to build robust scalable infrastructures.