Prophecy: Using history for high-throughput fault tolerance

Research output: Contribution to conferencePaperpeer-review


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. Along the way, we derive a distributed variant of Prophecy that achieves the same consistency but without any trusted components. A 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. As Prophecy is most effective when state updates are rare, we finally present a measurement study of popular websites that demonstrates a large proportion of static data.

Original languageEnglish (US)
Number of pages16
StatePublished - Jan 1 2019
Event7th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2010 - San Jose, United States
Duration: Apr 28 2010Apr 30 2010


Conference7th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2010
Country/TerritoryUnited States
CitySan Jose

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering


Dive into the research topics of 'Prophecy: Using history for high-throughput fault tolerance'. Together they form a unique fingerprint.

Cite this