2.3 Basic Protocol

Purpose

In the preliminary protocol, a priest must record (i) the number of every ballot he has initiated, (ii) every vote he has cast, and (iii) every LastVote message he has sent. Keeping track of all this information would have been difficult for the busy priests. The Paxons therefore restricted the preliminary protocol to obtain the more practical basic protocol in which each priest p had to maintain only the following information in the back of his ledger:

$lastTried[p]$ The number of the last ballot that p tried to initiate, or −$\infty$ if there was none.

$prevVote[p]$ The vote cast by p in the highest-numbered ballot in which he voted, or −$\infty$ if he never voted.
Nota Bene: A vote includes both the ballot number and the decree

$nextBal[p]$ The largest value of b for which p has sent a $LastVote(b, v)$ message, or −$\infty$ if he has never sent such a message.

LAMPORT, P. 11 — §2.3

      The basic protocol is largely the same as the preliminary protocol but
      introduces explicit bounds that encode stronger promises about ballot
      participation. These bounds simplify storage and make obsolete messages
      safe to ignore. Reduced message passing and fewer retries are consequences
      of these rules, not their primary goal. Safety is preserved, but progress
      is still not guaranteed, so livelock remains possible.
    

(1) $NextBallot(b)$
Priest $p$ chooses a new ballot number $b$ greater than $lastTried[p]$, sets $lastTried[p]$ to $b$, and sends a $NextBallot(b)$ message to some set of priests

Unlike in the preliminary protocol there is now a guarantee that the ballot sent will be greater than the last known ballot number. This will mean less useless ballot rounds clogging up the system.

(2) $LastVote(b, v)$
Upon receipt of a $NextBallot(b)$ message from $p$ with $b$ > $nextBal[q]$, priest $q$ sets $nextBal[q]$ to $b$ and sends a $LastVote(b, v)$ message to $p$, where $v$ equals $prevVote[q]$. (A $NextBallot(b)$ message is ignored if $b$ ≤ $nextBal[q]$.)

Conceptually this is the same as the preliminary protocol, but with an explicit promise: once a priest responds to a ballot number b, he will not respond to any smaller one. Messages are ignored because acting on them would violate that promise.

(3) $BeginBallot(b, d)$
After receiving a $LastVote(b, v)$ message from every priest in some majority set $Q$, where $b$ = $lastTried[p]$, priest $p$ initiates a new ballot with number $b$, quorum $Q$, and decree $d$, where $d$ is chosen to satisfy B3. He then sends a $BeginBallot(b, d)$ message to every priest in $Q$.

The only difference is the check to make sure the messages being sent back are from the latest ballot, if not they are ignored to cut down on unneeded message passing.

(4) $Voted(b, q)$
Upon receipt of a $BeginBallot(b, d)$ message with $b$ = $nextBal[q]$, priest $q$ casts his vote in ballot number $b$, sets $prevVote[q]$ to this vote, and sends a $Voted(b, q)$ message to $p$. (A $BeginBallot(b, d)$ message is ignored if $b $\neq$ nextBal[q]$.)

The check that $b = nextBal[q]$ enforces the promise made in step (2). If a higher ballot has been observed, participating in this one would violate that promise, so the vote is refused.

(5) $Success(d)$
If $p$ has received a $Voted(b, q)$ message from every priest $q$ in $Q$ (the quorum for ballot number $b$), where $b$ = $lastTried[p]$, then he writes $d$ (the decree of that ballot) in his ledger and sends a $Success(d)$ message to every priest.

Another check to make sure that all the messages are of the latest round.

(6) Upon receiving a $Success(d)$ message, a priest enters decree $d$ in his ledger.

The node will record given decree. Notice it does not need the ballot number 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.