Basic Paxos in Action

We learned the rules for the basic Paxos algorithm in the previous lesson. In this lesson, we will see those rules in action by running Paxos through three different scenarios. We will also see a situation where Paxos makes no progress. Lastly, we will present a solution to making progress and a complete Paxos protocol simulation involving all three roles: proposers, acceptors, and learners. This will also show the role of learners in knowing the current status of a slot's chosen value.

Previous value already chosen

Let's see what happens when a value has already been chosen, and a new proposer comes in even with a higher proposal number. According to the rules, the new proposer is obligated to acknowledge the already chosen value and cannot enforce its own value.

Previous value not chosen, but new proposer sees it

Due to network delays, messages can reach different servers at different times. The messages of different servers can intermingle. Even specific servers might take different times to process and act on a request due to variable load conditions. In the following example, server 5's proposal sees an older proposal value being accepted at server 3. As per the rules, server 5 acknowledges the value that has been accepted at server 3.

Previous value not chosen, new proposer doesn't see it

It might be possible that the proposer at server 5 contacts a majority but does not yet see a ...