Scalable Byzantine Fault Tolerance

Byzantine fault-tolerant (BFT) replication has enjoyed a series of performance improvements, but remains costly due to its replicated work. We eliminate this cost for read-mostly workloads through Prophecy, a system that interposes itself between clients and any replicated service. At Prophecy’s core is a trusted sketcher component, designed to extend the semi-trusted load balancer that mediates access to an Internet service. The sketcher performs fast, load-balanced reads when results are historically consistent, and slow, replicated reads otherwise.

Despite its simplicity, Prophecy provides a new form of consistency called delay-once consistency:  informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times.  Along the way, we derive a distributed variant of Prophecy that achieves the same consistency but without any trusted components.

Our prototype implementation demonstrates Prophecy’s high throughput compared to BFT systems. We also describe and evaluate Prophecy’s ability to scale-out to support large replica groups or multiple replica groups.


  • Prophecy: Using History for High-Throughput Fault Tolerance. Siddhartha Sen, Wyatt Lloyd, and Michael J. Freedman. Proc. 7th USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI ‘10), San Jose, CA, April 2010. [pdf]


Special thanks to the National Science Foundation (CAREER award #0953197) for funding. None of the work described here reflects the opinions or positions of this organization.