“Paxos Made Simple”

Paxos addresses the issue of consensus among a group of actors (getting them all to accept the same value). The algorithm is roughly as follows:
- There are three basic roles for agents: proposers, acceptors, and learners

There are two stages: proposal and acceptance stages

Proposal phase:
- First a proposer selects a proposal number n and sends the request to a majority of acceptors
- If an acceptor receives a request with a number n great than any request it has already responded to, it responds with a promise not to accept any more proposals numbered less than n with the highest-numbered proposal it has accepted

Acceptance phase:
- If the proposer receives a response to its request from a majority of acceptors, it sends an accept request to the acceptors with the value v, where v is the value of the highest-number proposal among the responses
- If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it already responded to a request with a number > n
It’s important to have a majority of nodes to accept or else if you encounter partitions, nodes could think that they had a consensus when they actually don’t.

The problem that this paper addresses is certainly real: in a distributed environment it is very problematic for machines to agree on values. The main point of the paper was to explain and prove the algorithm in a straightforward way, since earlier papers made the algorithm seem overly hard (though I think it’s hard to argue that the algorithm/explanation the paper presents is “simple” by any stretch of the imagination!).  I found the organization of the paper a bit unintuitive--the proof leads up to a description of the algorithm, so you don’t necessarily know beforehand where everything is leading (unless you already know the algorithm!). A brief description of the way Paxos works at the beginning would have been helpful. The system doesn’t seem to have any inherent tradeoffs (it solves the problem it sets out to solve), except for complexity. That said, this paper and Paxos itself have been very influential (as we see in the other papers), so there is no question of the paper’s relevance.