Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms

• Published in: ACM computing surveys 2024-05, Vol.56 (5), p.1-41, Article 134
• Main Authors: Zhang, Gengrui, Pan, Fei, Mao, Yunhao, Tijanic, Sofia, Dang’ana, Michael, Motepalli, Shashank, Zhang, Shiquan, Jacobsen, Hans-Arno
• Format: Article
• Language: English
• Subjects: Algorithms; Computer science; Computing methodologies; Cryptography; Distributed computing methodologies; Fault tolerance; Message passing
• ISSN: 0360-0300; 1557-7341
• DOI: 10.1145/3636553

Byzantine fault-tolerant (BFT) consensus algorithms are at the core of providing safety and liveness guarantees for distributed systems that must operate in the presence of arbitrary failures. Recently, numerous new BFT algorithms have been proposed, not least due to the traction blockchain technologies have garnered in the search for consensus solutions that offer high throughput, low latency, and robust system designs. In this article, we conduct a systematic survey of selected and distinguished BFT algorithms that have received extensive attention in academia and industry alike. We perform a qualitative comparison among all algorithms we review considering message and time complexities. Furthermore, we provide a comprehensive, step-by-step description of each surveyed algorithm by decomposing them into constituent subprotocols with intuitive figures to illustrate the message-passing pattern. We also elaborate on the strengths and weaknesses of each algorithm compared to the other state-of-the-art approaches.