Intricacies of Paxos

The Paxos protocol was considered to be difficult to understand by many people.

One of the reasons for this is the inherent complexity of the consensus problem, which in turn originates from the increased concurrency and large state space of distributed systems.

This lesson will cover some edge cases and how Paxos handles them. Of course, we will not be able to cover all the possible cases since that would be a much bigger undertaking. The examples presented in this lesson will help us understand the basic parts of the protocol and give us a starting point for exploring any other cases we might think of.

For all of the examples presented in this lesson, we will assume that the nodes play all the roles of the protocol, thus being proposers, acceptors, and learners at the same time, to simplify our explanations.

Keep in mind that this is a realistic assumption since many implementations of the Paxos protocol follow this approach.