Bolt-Dumbo Transformer: Asynchronous Consensus As Fast As Pipelined BFT

Optimistic asynchronous atomic broadcast was proposed to improve the performance of asynchronous protocols while maintaining their liveness in unstable networks (Kursawe-Shoup, 2002; Ramasamy-Cachin, 2005). They used a faster deterministic protocol in the optimistic case when the network condition remains good, and can safely fallback to a pessimistic path running asynchronous atomic broadcast once the fast path fails to proceed. Unfortunately, besides that the pessimistic path is slow, existing fallback mechanisms directly use a heavy tool of asynchronous multi-valued validated Byzantine agreement (MVBA). When deployed on the open Internet, which could be fluctuating, the inefficient fallback may happen frequently thus the benefits of adding the optimistic path are eliminated. We give a generic framework for practical optimistic asynchronous atomic broadcast. A new abstraction of the optimistic case protocols, which can be instantiated easily, is presented. More importantly, it enables us to design a highly efficient fallback mechanism to handle the fast path failures. The resulting fallback replaces the cumbersome MVBA by a variant of simple binary agreement only. Besides a detailed security analysis, we also give concrete instantiations of our framework and implement them. Extensive experiments show that our new fallback mechanism adds minimal overhead, demonstrating that our framework can enjoy both the low latency of deterministic protocols and robust liveness of randomized asynchronous protocols in practice.