Unstick Yourself: Recoverable Byzantine Fault Tolerant Services
Tuan Tran, Faisal Nawab, Peter Alvaro, Owen Arden · 2023
Byzantine fault tolerant (BFT) state machine replication (SMR) protocols that can tolerate up to$f$failures in a configuration of$n=3f+1$replicas cannot make any liveness guarantee once the number of faults surpasses f, even if some of these faults are benign crash faults. We argue that this weakness makes BFT protocols impractical in real-world deployments where faults accumulate over time. In this paper, we present a new reconfiguration mechanism, Phoenix, that builds on the pre-existing fault detection and reconfiguration mechanisms of BFT protocols to remove faulty replicas proactively using a trusted (but limited) configuration manager. We show that Phoenix can recover from$f_{B}$Byzantine faults and$f_{C}$crash faults, where$f_{C}\leq f_{B}$, if the system deploys$n=3f_{B}+f_{C}+1$replicas. If a synchronous network connection is guaranteed between replicas and the configuration manager during reconfiguration, a synchronous variant of Phoenix needs only$n=3f_{B}+1$replicas to achieve the same recoverability. To validate our approach, we implement Phoenix as an extension of the BFT-SMaRT library.