Prophecy: Using history for high-throughput 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. 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.