The Next 700 BFT Protocols

Modern Byzantine fault-tolerant state machine replication (BFT) protocols involve about 20,000 lines of challenging C++ code encompassing synchronization, networking and cryptography. They are notoriously difficult to develop, test and prove. We present a new abstraction to simplify these tasks. We treat a BFT protocol as a composition of instances of our abstraction. Each instance is developed and analyzed independently. To illustrate our approach, we first show how our abstraction can be used to obtain the benefits of a state-of-the-art BFT protocol with much less pain. Namely, we develop AZyzzyva, a new protocol that mimics the behavior of Zyzzyva in best-case situations (for which Zyzzyva was optimized) using less than 24% of the actual code of Zyzzyva. To cover worst-case situations, our abstraction enables to use in AZyzzyva any existing BFT protocol, typically, a classical one like PBFT which has been tested and proved correct. We then present Aliph, a new BFT protocol that outperforms previous BFT protocols both in terms of latency (by up to 30%) and throughput (by up to 360%). The development of Aliph required two new instances of our abstraction. Each instance contains less than 25% of the code needed to develop state-of-the- art BFT protocols.

Published in:
Proceedings of the 5th ACM European conference on Computer systems
Presented at:
5th ACM EuroSys Conference, Paris, France, April 13-16, 2010
Best Paper Award

Note: The status of this file is: Involved Laboratories Only

 Record created 2010-02-08, last modified 2018-03-17

Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)