Prophecy: Using history for high-throughput fault tolerance

Research output: Contribution to conferencePaper

Abstract

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)
Pages345-360
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

Conference

Conference7th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2010
CountryUnited States
CitySan Jose
Period4/28/104/30/10

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering

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

  • Cite this

    Sen, S., Lloyd, W., & Freedman, M. J. (2019). Prophecy: Using history for high-throughput fault tolerance. 345-360. Paper presented at 7th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2010, San Jose, United States.