# Generalized Paxos Made Byzantine
## 4 Crash Fault Tolerant Protocol
### Agreement Protocol
#### 4.1.2 Fast Ballots  
In contrast to classic ballots, fast ballots are able to leverage a weaker specification of generalized consensus, in terms of command ordering at different replicas, to allow for faster execution of commands in some cases. The basic idea of fast ballots is that proposers contact the acceptors directly (code for acceptors in Algorithm 4), bypassing the leader (code for leaders in Algorithm 5), and then the acceptors send their votes on proposals to the learners. If a learner can gather \(N-f\) votes for a sequence (or an equivalent one), then it is learned. If, however, a conflict exists between sequences then they will not be considered equivalent and at most one of them will gather enough votes to be learned. Conflicts are dealt with by maintaining the proposals at the acceptors so they can be sent to the leader and learned in the next classic ballot. This differs from Fast Paxos where recovery is performed through an additional round-trip [12]. ```
1:\(leader=\bot,bal_{a}=0,val_{a}=\bot,fast\_bal=\bot\)
2:upon receive(\(P1A,ballot\)) from leader do
3:\(\textsc{phase\_1b}(ballot)\)
4:upon receive(\(FAST,ballot\)) from leader do
5:\(fast\_bal[ballot]=true\)
6:
7:upon receive(\(P2A\_CLASSIC,ballot,value\)) from leader do
8:\(\textsc{phase\_2b\_classic}(ballot,value)\)
9:
10:upon receive(\(P2A\_FAST,ballot,value\)) from proposer p do
11:\(\textsc{phase\_2b\_fast}(ballot,value)\)
12:
13:function\(\textsc{phase\_1b}(ballot)\)
14:if\(bal_{a}<ballot\)then
15:\(\textsc{send}(P1B,ballot,bal_{a},val_{a})\) to leader
16:\(bal_{a}=ballot\)
17:\(val_{a}=\bot\)
18:endfunction
19:
20:function\(\textsc{phase\_2b\_classic}(ballot,value)\)
21:if\(ballot\geq bal_{a}\) and \(val_{a}=\bot\)then
22:\(bal_{a}=ballot\)
23:if\(\textsc{isUniversallyCommutative}(value)\)then
24:\(\textsc{send}(P2B,ballot,value)\) to learners
25:else
26:\(val_{a}[ballot]=value\)
27:\(\textsc{send}(P2B,ballot,value)\) to learners
28:endfunction
29:
30:function\(\textsc{phase\_2b\_fast}(ballot,value)\)
31:if\(ballot=bal_{a}\) and \(fast\_bal[bal_{a}]\)then
32:if\(\textsc{isUniversallyCommutative}(value)\)then
33:\(\textsc{send}(P2B,ballot,value)\) to learners
34:else
35:\(val_{a}[bal_{a}]=\textsc{merge\_sequences}(val_{a}[bal_{a}],value)\)
36:\(\textsc{send}(P2B,bal_{a},val_{a}[bal_{a}])\) to learners
37:endfunction
```  
**Algorithm 4** Generalized Paxos--Acceptor a  
Next, we explain each of these steps in more detail. Step 1: Proposer to acceptorsTo initiate a fast ballot, the leader informs both proposers and acceptors that the proposals may be sent directly to the acceptors. Unlike classic ballots, where the sequence proposed by the leader consists of the commands received from the proposers appended to previously proposed commands, in a fast ballot proposals can be sent to the acceptors in the form of either a single command or a sequence to be appended to the command history. These proposals are sent directly from the proposers to the acceptors. ```
1:\(learned=\bot,messages=\bot\)
2:upon receive(\(P2B,ballot,value\)) from acceptor \(a\)do
3:messages[ballot][value][a] = true
4:if(messages[ballot][value]) \(\geq\)\(N-f\) or (isUniversallyCommutative(value) and #(messages[ballot][value]) >\(f\))then
5:\(learned=\textsc{merge\_sequences}(learned,value)\)
```  
**Algorithm 5** Generalized Paxos--Learner l  
**Step 2: Acceptors to learners. ** Acceptors append the proposals they receive to the proposals they have previously accepted in the current ballot and broadcast the result to the learners. Similarly to what happens in classic ballots, a _phase 2b_ message is sent from acceptors to learners, containing the current ballot number and the command sequence. However, since commands (or sequences of commands) are concurrently proposed, acceptors can receive and vote for non-commutative proposals in different orders. To ensure safety, correct learners must learn non-commutative commands in a total order. To this end, a learner must gather \(N-f\) votes for equivalent sequences.