BVP: Byzantine Vertical Paxos

Details

In this paper, we consider the challenge of driving a serious, industrial-grade infrastructure for Byzantine agreement and state machine replication. We focus on two aspects, elasticity (dynamic reconfiguration) and throughput. We introduce Byzantine Vertical Paxos (BVP), a family of protocols designed to address both goals. BVP is built of the foundations of Vertical Paxos (VP) \cite{VP}, which separates a solution into two modes. The first mode is a simple steady state protocol, and the second is a reconfiguration protocol. Often, the steady state protocol is just primary-backup or its generalization to multiple nodes via Chain Replication (CR)~\cite{CR} or Two Phase Commit (2PC). The second mode is a Paxos based reconfiguration engine. The advantage of VP is that the steady state can be optimized for high throughput and the heavy lifting on Paxos is used only when reconfiguration is needed. Here we introduce BVP, a Byzantine variant of VP. As in VP, in BVP the steady state mode can be simple and highly optimized despite the Byzantine settings. A separate consensus engine is used for reconfiguration. In many realistic settings the network is synchronous. In this case, our steady-state solution requires only $f+1$ replicas, and $2f+1$ replicas for reconfiguration. In fact, we don't really require the system to be synchronous in steady state, only to have some out-of-band synchronous control channel for reconfiguration purposes. Yet other settings may have secure hardware devices such as TPMs. Again we provide an $f+1$ steady-state solution here.