# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### Agreement Protocol
```
1:\(\textit{subspictions}=\bot\), \(\textit{new\_view}=\bot\), \(\textit{leader}=\bot\), \(\textit{view}=0,\textit{bal}_{a}=0\), \(\textit{val}_{a}=\bot\), \(\textit{fast\_bal}=\bot\), \(\textit{checkpoint}=\bot\)
2:upon\(\textit{suspect\_leader}\)do
3:if\(\textit{subspictions}[p]\
eq\textit{true}\)then
4:\(\textit{suspictions}[p]=\textit{true}\)
5:\(\textit{proof}=\langle\textit{suspicion},\textit{view}\rangle_{\textit{ priv}_{a}}\)
6:\(\textit{send}(\textit{SUSPICION},\textit{view},\textit{proof})\)
7:
8:upon\(\textit{receive}(\textit{SUSPICION},\textit{view}_{i},\textit{proof})\) from acceptor \(i\)do
9:if\(\textit{view}_{i}\
eq\textit{view}\)then
10:return
11:if\(\textit{proof}_{\textit{guh}}==\langle\textit{suspicion},\textit{view}\rangle\)then
12:\(\textit{suspictions}[i]=\textit{proof}\)
13:if\(\textit{suspictions})>f\)and\(\textit{new\_view}[\textit{view}+1][p]==\bot\)then
14:\(\textit{change\_proof}=\langle\textit{view\_change},\textit{view}+1]_{\textit{ priv}_{a}}\)
15:\(\textit{new\_view}+1[p]=\textit{change\_proof}\)
16:\(\textit{send}(\textit{VIEW\_CHANGE},\textit{view}+1,\textit{suspictions}, \textit{change\_proof})\)
17:
18:upon\(\textit{receive}(\textit{VIEW\_CHANGE},\textit{new\_view}_{i},\textit{suspictions},\textit{change\_proof}_{i})\) from acceptor \(i\)do
19:if\(\textit{new\_view}_{i}\leq\textit{view}\)then
20:return
21:\(\textit{valid\_proofs}=0\)
22:for\(p\)in\(\textit{acceptors}\)do
23:\(\textit{proof}=\textit{suspictions}[p]\)
24:\(\textit{last\_view}=\textit{new\_view}-1\)
25:if\(\textit{proof}_{\textit{guh}}==\langle\textit{suspicion},\textit{last\_view}\rangle\)then
26:\(\textit{valid\_proofs}+=1\)
27:
28:if\(\textit{valid\_proofs}\leq f\)then
29:return
30:
31:\(\textit{new\_view}[\textit{new\_view}_{i}][i]=\textit{change\_proof}_{i}\)
32:if\(\textit{new\_view}[\textit{view}_{i}][i]==\bot\)then
33:\(\textit{change\_proof}=\langle\textit{view\_change},\textit{new\_view}_{i} \rangle_{\textit{privv}_{a}}\)
34:\(\textit{new\_view}[\textit{view}_{i}][i]=\textit{change\_proof}\)
35:\(\textit{send}(\textit{VIEW\_CHANGE},\textit{view}_{i},\textit{suspictions}, \textit{change\_proof})\)
36:
37:if\(\textit{(new\_view}[\textit{new\_view}]_{i})\geq N-f\)then
38:\(\textit{view}=\textit{view}_{i}\)
39:\(\textit{leader}=\textit{view}\ mod\ N\)
40:\(\textit{suspictions}=\bot\)
41:\(\textit{send}(\textit{LEADER},\textit{view},\textit{new\_view}[\textit{view}_{i}])\) to leader
42:
43:\(\textit{send}(\textit{LEADER},\textit{view},\textit{new\_view}[\textit{view}_{i}])\) to leader
44:
45:\(\textit{send}(\textit{LEADER},\textit{view},\textit{new\_view}[\textit{view}_{i}])\) to leader
46:



#### 5.3.1 Fast Ballots

Fast ballots leverage the weaker specification of generalized consensus (compared to classic consensus) in terms of command ordering at different replicas, to allow for the faster execution of commands in some cases. The basic idea of fast ballots is that proposers contact the acceptors directly, bypassing the leader, and then the acceptors send their vote for the current sequence to the learners. If a conflict exists and progress is not being made, the protocol reverts to using a classic ballot. This is where generalized consensus allows us to avoid falling back to this slow path, namely in the case where commands that ordered differently at different acceptors commute (code for acceptors in Algorithm 9). However, this concurrency introduces safety problems even when a quorum is reached for some sequence. If we keep the original Fast Paxos message pattern [12], it is possible for one sequence \(s\) to be learned at one learner \(l_{1}\) while another non-commutative sequence \(s^{\prime}\) is learned before \(s\) at another learner \(l_{2}\). Suppose \(s\) obtains a quorum of votes and is learned by \(l_{1}\) but the same votes are delayed indefinitely before reaching \(l_{2}\). In the next classic ballot, when the leader gathers a quorum of _phase 1b_ messages it must arbitrate an order for the commands that it received from the acceptors and it does not know the order in which they were learned.