Paxos Made Simple

Paxos Made Simple deals with the distributed consensus problem. In the
algorithm, there are proposers, acceptors, and learners. Proposers send prepare
requests with a number n to the acceptors. The acceptors keep track of
the highest n they have seen and send promises saying that they will not
accept any proposals with a lower n value. Proposers who receive promises
respond back with a value v and the n as their proposal.
Eventually, a majority acceptors come to agree on the same value. However, Paxos
is open a livelock scenario in which two proposers keep sending prepares with
numbers greater than before. For this scenario, one can just have a
distinguished proposer to ensure progress.

Paxos Made Practical shows a detailed implementation of Paxos. However, the
implementation seems to be much more difficult than the algorithm presented in
Paxos Made Simple. It seems this is because implementation must account for the
dynamic addition and subtraction of nodes in the group, and things like
timestamping views are necessary to make sure the nodes among the group have the
same state, as required by the RSM model.

The Chubby lock is meant to provide a simpler implementation for the same sort
of distributed decision making that Paxos provides. However, with the Chubby
lock, the client does not need its own library to synchronize with the other
nodes; instead you access a centralized a lock server. The lock server also has
failover mechanisms to cope with failing masters through leader selection.

Overall, distributed decision making is obviously a useful functionality,
especially for the RSM model, and Paxos and Chubby locks provide ways to do
this. However, it seems Paxos may be too complicated for practical
implementation, and services like Chubby may be more realistic.