Byzantine Fault-Tolerant Distributed Computing: Reconfiguration and Consensus

Byzantine fault-tolerance is a critical mechanism allowing software engineers to build distributed systems resilient to numerous kinds of hardware failures, software bugs, and security breaches. Depending on the environment, different models are used to design distributed protocols. Notably, there is a huge gap between the so-called asynchronous and partially-synchronous models. The latter allows for deterministic solutions of the famous consensus problem whereas the former does not. In this thesis, one important problem for each of the two models is addressed, the ultimate goal being to make both types of algorithms more applicable in practice. In the asynchronous model, the problem of reconfiguration is considered. Most known Byzantine fault-tolerant algorithms are designed with the assumption that the set of processes executing the protocol is fixed and known a priori. While being very convenient for algorithm designers, this assumption is not very realistic. In practice, servers often need to be replaced, repaired, or added for greater fault tolerance. In this thesis, the first asynchronous reconfiguration protocol tolerating Byzantine failures is presented. In the partially-synchronous model, on the other hand, reconfiguration can be performed much easier thanks to the possibility to solve consensus. However, Byzantine fault-tolerant consensus algorithms have a reputation of being much slower than their crash fault-tolerant counterparts. To close this gap, the class of fast Byzantine consensus algorithms has emerged. These algorithms aim at solving the Byzantine consensus with the same latency as crash fault-tolerant solutions. However, this improved latency comes at the cost of decreased fault tolerance. In this thesis, a new fast Byzantine consensus algorithm that has better resilience than any of the previously existing ones is presented. Moreover, the algorithm comes with proof that its resilience is optimal. The surprising discovery is that, in the special yet very important in practice case when only one Byzantine failure is tolerated, the algorithm presented in this thesis requires only 4 processes, which remains optimal even if we allow for suboptimal latency. All previously known fast Byzantine consensus algorithms required at least 6 processes in this case.