Distributed consensus revised – Part I
In the face of this, an algorithm for consensus must meet three safety requirements and two progress requirements:
The first part of the thesis examines the Paxos family of algorithms, and is a great resource for navigating this complex space. These are important results since as well as being notoriously difficult to understand and to implement, Paxos has some well-known and not-so-well-known limitations:
The reliance on majority agreement means that the Paxos algorithm is slow to reach decisions… systems are limited in scale, often to three or five participants, as each additional participant substantially decreases overall performance. Removing that single point of failure and supporting multiple acceptors leads us to Paxos…
Unoptimised classic Paxos can reach agreement with two round trips to the majority of acceptors, and three synchronous writes to persistent storage.