2.2 Preliminary Protocol
LAMPORT, P. 11 — §2.2Steps 1–6 describe how an individual ballot is conducted. The preliminary protocol allows any priest to initiate a new ballot at any time. Each step maintains B1(B)– B3(B), so the entire protocol also maintains these conditions. Since a priest enters a decree in his ledger only if it is the decree of a successful ballot, Theorem 1 implies that the priests’ ledgers are consistent. The protocol does not address the question of progress.
This protocol is used to demonstrate that the paxos protocol is safe. It does not yet prove that deadlocks will not happen only that decrees will not be overwritten.
Priest $p$ chooses a new ballot number b and sends a $NextBallot(b)$ message to some set of priests.
Said set of priest can and usually includes itself. You can think of message functions as small data payloads including all the needed data. Notice that the ballot number b can be any number including ones lower than previously used or even ones previously used. This is why this protocol is about safety not about progress.
A priest $q$ responds to the receipt of a $NextBallot(b)$ message by sending a $LastVote(b, v)$ message to $p$, where $v$ is the vote with the largest ballot number less than $b$ that $q$ has cast, or his null vote null $q$ if $q$ did not vote in any ballot numbered less than $b$.
The $NextBallot$ message is essentially a query: "What is the largest vote below this ballot number that you have cast?" Step three deals with the collected data sent back through these $LastVote(b, v)$ messages.
After receiving a $LastVote(b, v)$ message from every priest in some majority set $Q$, priest $p$ initiates a new ballot with number $b$, quorum $Q$, and decree $d$, where $d$ is chosen to satisfy B3. He then records the ballot in the back of his ledger and sends a $BeginBallot(b, d)$ message to every priest in $Q$.
If there are enough nodes that meet the quorum threshold, the node will broadcast to all nodes that replied with LastVote with a BeginBallot message that contains the ballot id and decree that fulfils B3.
For safety, if any nodes have voted, $p$ must assume those votes may be accepted eventually. Only if no votes have been recorded from any nodes can $p$ freely choose a decree.
Upon receipt of the $BeginBallot(b, d)$ message, priest $q$ decides whether or not to cast his vote in ballot number $b$. (He may not cast the vote if doing so would violate a promise implied by a $LastVote(b', v')$ message he has sent for some other ballot.) If $q$ decides to vote for ballot number $b$, then he sends a $Voted(b, q)$ message to p and records the vote in the back of his ledger.
When a node receives BeginBallot and has not recorded a ballot larger than the ballot id given in the message it will send back Voted and record this vote.
If p has received a $Voted(b, q)$ message from every priest $q$ in $Q$ (the quorum for ballot number $b$), then he writes $d$ (the decree of that ballot) in his ledger and sends a $Success(d)$ message to every priest.
If quorum threshold is again reached the node will record the decree as successful and send another broadcast to every known node to update their ledger even if they did not participate in the vote
The node will record given decree. Notice it does not need the ballot id for safety. This is due to the quorum rule that already makes sure at least one of the responding nodes will have that information for any future ballot.