# Generalized Paxos Made Byzantine
## 1 Introduction  
The evolution of the Paxos [1] protocol is a unique chapter in the history of Computer Science. It was first described in 1989 through a technical report [2], and was only published a decade later [1]. Another long wait took place until the protocol started to be studied in depth and used by researchers in various fields, namely the distributed algorithms [3] and the distributed systems [4] research communities. In addition, finally, another decade later, the protocol made its way to the core of the implementation of the services that are used by millions of people over the Internet, in particular since Paxos-based state machine replication is the key component of Google's Chubby lock service [5], or the open source ZooKeeper project [6], used by Yahoo! among others. Arguably, the complexity of the presentation may have stood in the way of a faster adoption of the protocol, and several attempts have been made at writing more concise explanations of it [7; 8]. More recently, several variants of Paxos have been proposed and studied. Two important lines of research can be highlighted in this regard. First, a series of papers hardened the protocol against malicious adversaries by solving consensus in a Byzantine fault model [9; 10]. The importance of this line of research is now being confirmed as these protocols are now in widespread use in the context of cryptocurrencies and distributed ledger schemes such as blockchain [11]. Second, many proposals target improving the Paxos protocol by eliminating communication costs [12], including an important evolution of the protocol called Generalized Paxos [13], which has the noteworthy aspectof having lower communication costs by leveraging a specification that is weaker than traditional consensus. In particular, instead of forcing all processes to agree on the same value, it allows processes to pick an increasing sequence of commands that differs from process to process in that commutative commands may appear in a different order. The practical importance of such weaker specifications is underlined by a significant research activity on the corresponding weaker consistency models for replicated systems [14; 15]. In this paper, we draw a parallel between the evolution of the Paxos protocol and the current status of Generalized Paxos. In particular, we argue that, much in the same way that the clarification of the Paxos protocol contributed to its practical adoption, it is also important to simplify the description of Generalized Paxos. Furthermore, we believe that evolving this protocol to the Byzantine model is an important task, since it will contribute to the understanding and also open the possibility of adopting generalized Paxos in scenarios such as a Blockchain deployment. As such, the paper makes several contributions, which are listed next. * We present a simplified version of the specification of Generalized Consensus, which is focused on the most commonly used case of the solutions to this problem, which is to agree on a sequence of commands;
* we present a simplified version of the Generalized Paxos protocol, complete with pseudocode;
* we extend the Generalized Paxos protocol to the Byzantine fault model;
* we present a description of the Byzantine Generalized Paxos protocol including the respective pseudocode, in order to make it easier to implement;
* we prove the correctness of the Byzantine Generalize Paxos protocol;
* and we discuss several extensions to the protocol in the context of relaxed consistency models and fault tolerance. The remainder of the paper is organized as follows: Section 2 is a detailed overview of Paxos and related protocols that inspired the algorithm in this paper. Section 3 introduces the model and specification of Generalized Paxos. Section 4 presents a simplified version of the Generalized Paxos protocol in the crash fault model. Section 5 presents the Generalized Paxos protocol that is resilient against Byzantine failures.