Section 3.1. Multiple Paxos Protocol
As in the Synod protocol, a president was elected. Anyone who wanted a decree passed would inform the president, who would assign a number to the decree and attempt to pass it. Logically, the parliamentary protocol used a separate instance of the complete Synod protocol for each decree number. However, a single president was selected for all these instances, and he performed the first two steps of the protocol just once.LAMPORT, P. 15 — §3.1
The key line here is "he performed the first two steps of the protocol once". To cut down on message passing once a ballot was promised, if there are no other competing nodes steps 3-6 are unlikely to be contested when a stable leader exists.
A newly elected president $p$ can send to some set of legislators a single message that serves as the $NextBallot(b)$ message for all instances of the Synod protocol. (There are an infinite number of instances—one for each decree number.) A legislator $q$ can reply with a single message that serves as the $LastVote$ messages for step 2 of all instances of the Synod protocol. This message contains only a finite amount of information, since q can have voted in only a finite number of instances. When the new president has received a reply from every member of a majority set, he is ready to perform step 3 for every instance of the Synod protocol. For some finite number of instances (decree numbers), the choice of decree in step 3 will be determined by B3. The president immediately performs step 3 for each of those instances to try passing these decrees. Then, whenever he receives a request to pass a decree, he chooses the lowest-numbered decree that he is still free to choose, and he performs step 3 for that decree number (instance of the Synod protocol) to try to pass the decree.LAMPORT, P. 15 — §3.1
Instead of the message containing a single decree promise, the node can send a batch message to get a promise for each future $BeginBallot(d,b)$ message that will be sent for the same current ballot. No matter the size of the range that is asked the message will be of finite size since accepted decrees will be of a finite size. The batch can be of range 10 or range 124-$\infty$
There is no reason to go through the Synod protocol for a decree number whose outcome is already known. Therefore, if a newly elected president $p$ has all decrees with numbers less than or equal to $n$ written in his ledger, then he sends a $NextBallot(b)$ message that serves as a $NextBallot(b)$ message in all instances of the Synod protocol for decree numbers larger than n. In his response to this message, legislator $q$ informs p of all decrees numbered greater than n that already appear in $q$’s ledger (in addition to sending the usual $LastVote$ information for decrees not in his ledger), and he asks $p$ to send him any decrees numbered $n$ or less that are not in his ledger.LAMPORT, P. 15 — §3.1
For the batch call, the leader can claim all lastVoted(p) information for multiple instances using the same ballot number. Each legislator’s reply contains all votes they have cast in the past for those instances, enabling both the leader and other nodes to catch up. The leader can get any unknown decrees further along in its' $NextBallot$ call and other nodes can get previous decrees it might be missing.
Lamport also brings up the idea of a No-OP to fill gaps.
The ides of February is national olive day a traditional decree that made absolutely no difference to anyone in Paxos. In general, a new president would fill any gaps in his ledger by passing the “olive day” decree.LAMPORT, P. 16 — §3.1
When new leaders are elected, gaps may exist in the ledger that were never filled or were lost during transitions. These gaps are filled with a No-Op, a value chosen by consensus that has no operational effect, to ensure the sequence of instances remains consistent.