# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### Agreement Protocol
At any given instant, \(\forall s\in\mathcal{P},\forall l_{i}\in\mathcal{L},learned(l_{i},s)\implies \mathit{proposed}(s)\)

**Proof:** By 1 and 2. 4. Q.E.D. ### Stability

**Theorem 3**. : _If learned\({}_{l}=s\) then, at all later times, \(s\sqsubseteq learned_{l}\), for any sequence \(s\) and correct learner \(l\)._

**Proof:** By Algorithm 10 lines [12; 18], a correct learner can only append new commands to its _learned_ command sequence. ### Liveness

**Theorem 4**. : _For any proposal \(s\) from a correct proposer, and correct learner \(l\), eventually learned\({}_{l}\) contains \(s\)._

**Proof:**

1. \(\forall\,l_{i}\in\mathcal{L},\forall s,x\in\mathcal{P},\exists\sigma\in \mathcal{P},\forall b\in\mathcal{B},maj\_accepted(s,b)\vee(min\_accepted(s,b) \wedge



### Handling Faults in the Fast Case

A result that was stated in the original Generalized Paxos paper [13] is that to tolerate \(f\) crash faults and allow for fast ballots whenever there are up to \(e\) crash faults, the total system size \(N\) must uphold two conditions: \(N>2f\) and \(N>2e+f\). Additionally, the fast and classic quorums must be of size \(N-e\) and \(N-f\), respectively. This implies that there is a price to pay in terms of number of replicas and quorum size for being able to run fast operations during faulty periods. An interesting observation from our work is that, since Byzantine fault tolerance already requires a total system size of \(3f+1\) and a quorum size of \(2f+1\), we are able to amortize the cost of both features, i.e., we are able to tolerate the maximum number of faults for fast execution without paying a price in terms of the replication factor and quorum size. ### Extending the Protocol to Universally Commutative Commands

A downside of the use of commutative commands in the context of Generalized Paxos is that the commutativity check is done at runtime, to determine if non-commutative commands have been proposed concurrently. This raises the possibility of extending the protocol to handle commands that are universally commutative, i.e., commute with every other command. For these commands, it is known before executing them that they will not generate any conflicts, and therefore it is not necessary to check them against concurrently executing commands. This allows us to optimize the protocol by decreasing the number of phase \(2b\) messages required to learn to a smaller \(f+1\) quorum. Since, by definition, these sequences are guaranteed to never produce conflicts, the \(N-f\) quorum is not required to prevent learners from learning conflicting sequences. Instead, a quorum of \(f+1\)



**Author Contributions:** All the authors contribute equally to this work. **Funding:** The research of [PERSON] is funded by the European Research Council (ERC-2012-StG-307732) and by FCT (UID/CEC/50021/2013). **Conflicts of Interest:** The authors declare no conflict of interest. ## References

* (1) [PERSON] The Part-Time Parliament. _ACM Trans. Comput. Syst._**1998**, _16_, 133-169. [CrossRef]
* (2) [PERSON] _The Part-Time Parliament_; Technical Report; DEC SRC: Maynard, MA, USA, 1989. * (3) [PERSON]; [PERSON]; [PERSON] Revisiting the Paxos Algorithm. In _Distributed Algorithms, Proceedings of the 11 th Workshop on Distributed Algorithms, Saarbrucken, Germany, 24-26 September 1997;_ Springer: Berlin/Heidelberg, Germany, 1997; LNCS 1320. * (4) [PERSON]; [PERSON]: Distributed Virtual Disks. In Proceedings of the 7 th International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, USA, 1-4 October 1996. * (5) [PERSON] The Chubby Lock Service for Loosely-coupled Distributed Systems. In Proceedings of the 7 th Symposium on Operating Systems Design and Implementation, Seattle, WA, USA, 6-8 November 2006. * (6) [PERSON]; [PERSON]; [PERSON]: High-performance Broadcast for Primary-backup Systems. In Proceedings of the 41 st International Conference on Dependable Systems and Networks, Hong Kong, China, 27-30 June 2011. * (7) [PERSON] [PERSON] Paxos Made Simple.