# Generalized Paxos Made Byzantine
## 4 Crash Fault Tolerant Protocol
### Agreement Protocol
#### 4.1.1 Classic Ballots  
As previously mentioned, classic ballots work in a similar way to previous Paxos protocols. Therefore, we will highlight the points where Generalized Paxos departs from the Classic Paxos protocol, in particular where it is due to behaviors caused by our simplified specification of Generalized Paxos. In this part of the protocol, the leader continuously collects proposals by assembling commands received from the proposers in a sequence (cf. Algorithm 3). This sequence is built by appending arriving proposals to a sequence containing every proposal received since the previous ballot (this differs from classic Paxos, where it suffices to keep a single proposed value that the leader attempts to reach agreement on). When the next ballot is triggered, the leader starts the first phase by sending _phase 1a_ messages to all acceptors containing just the ballot number. Similarly to classic Paxos, acceptors reply with a _phase 1b_ message to the leader, which reports all sequences of commands they voted for. This message also implicitly conveys a promise not to participate in lower-numbered ballots, in order to prevent safety violations [2]. After gathering a quorum of \(N-f\)_phase 1b_ messages, the leader initiates _phase 2a_ by sending a message with a proposal to the acceptors. The procedure followed by the leader to construct this proposal is critical to prevent conflicts between sequences proposed in different ballots as well as to ensure liveness even when conflicts occur during fast ballots. There are two possible scenarios when observing the quorum \(Q\) of gathered _phase 1b_ messages: either there is one reported sequence \(s\) that was voted for at least \(f+1\) acceptors in the latest ballot or there is none. If such a sequence exists then it is guaranteed to be the only one that may have been learned. Since \(2f+1\) votes are necessary for any sequence to be learned and at least \(f+1\) acceptors voted for \(s\) then any other non-commutative sequence gathered at most \(2f\) votes, which is insufficient for it to be learned. If no sequence in the quorum gathered \(f+1\) votes then the leader can be sure that no value was or will be learned in that ballot. Since any sequence present in the quorum gathered at most \(f\) votes and there are only \(f\) acceptors outside of it, any sequence gathered at most \(2f\) votes, which is also not enough for it to be learned. However, even if the latest ballot didn't result in the learning of a value, the leader still has to pick the most up-to-date sequence in order to extend it with his proposals. Notice that, even though the latest ballot may not have reached consensus on a sequence, some previous ballot did and the _phase 2b_ quorum of that ballot intersects in the current quorum of _phase 1b_ messages in \(f+1\) acceptors. Therefore, we arrive at a well-defined value picking rule: given a quorum \(Q\) of _phase 1b_ messages, if some sequence \(s\) has more than \(f\) votes at the highest ballot in which some acceptor voted for, then that sequence is chosen as the prefix of the leader's proposal. If no such sequence exists, then the leader picks the longest prefix that is present in \(f+1\) sequences. It's possible to further simplify this rule by noting that the second case encases the first, since the longest possible prefix (\(\sqsubseteq\)) of a sequence is the sequence itself. More formally:  
**Leader rule**. For a quorum \(Q\) of _phase 1b_ messages, pick the longest prefix present in the sequences of at least \(f+1\) messages in \(Q\). After picking the most up-to-date sequence accepted by a quorum, the leader appends the commands present in _phase 1b_ messages that are not in the chosen sequence. This ensures liveness since any proposer's command that reaches more than \(f\) acceptors before the next ballot begins will eventually be included in an accepted proposal. After executing this rule, the leader simply appends the proposers' commands to the sequence and sends it to the acceptors in _phase 2a_ messages.