Prophecy: Using History for High-Throughput Fault Tolerance

Siddhartha Sen, Wyatt Lloyd, Michael J. FreedmanNSDI 2010 · OpenReview

Introduction

Byzantine Fault Tolerance (BFT) is the gold standard for reliability, ensuring system correctness even when nodes are malicious or misconfigured. However, the performance overhead of BFT is a significant barrier to adoption. In traditional BFT systems, every replica must execute every request to ensure consistency. This creates an "execution bottleneck": to tolerate a single faulty node, a system typically requires four replicas, effectively quadrupling the hardware cost for the same processing capacity. Prophecy addresses this bottleneck by enabling load-balanced reads through a history-based validation mechanism.

System Architecture and the Sketcher

The core innovation of Prophecy is the Sketcher, a component that sits between clients and the replicated service. The Sketcher maintains a compact history table of (request, response) pairs. To keep the memory footprint manageable, it stores "sketches"—cryptographic hashes (e.g., SHA-1) of responses—rather than the full data. This reduces the storage requirement for a massive dataset (e.g., 15TB of images) to a practical size (e.g., 27GB of sketches).

The Prophecy architecture featuring a trusted proxy with a sketcher component.

When a read request arrives, the Sketcher checks its history. If the request has been seen before, it initiates a "fast read" by querying only one replica for the full response and requesting short sketches from the others. If the returned sketches match the history, the result is accepted. This allows the system to distribute read requests across the cluster, scaling throughput linearly with the number of replicas.

Consistency and Comparison

Prophecy introduces delay-once consistency, a model that balances performance and safety. While slightly weaker than linearizability, it guarantees that a faulty node can only return a "stale" result (the previous valid version) and never arbitrary or malicious data. This is often an acceptable trade-off for web-scale services where high throughput is critical.

Comparison of properties across BFT, D-Prophecy, and Prophecy.

As shown in the table above, Prophecy differs from standard BFT and its distributed variant, D-Prophecy, by supporting unmodified clients and load-balanced reads while utilizing a small trusted component. Most web services already trust a load balancer or middlebox; Prophecy leverages this existing trust point to house the Sketcher, requiring less than 3,000 lines of code.

Evaluation and Key Results

The authors evaluated Prophecy using microbenchmarks and real-world applications like the Apache webserver. Key findings include:

  • Throughput Gains: Prophecy achieved 372% of the throughput of a read-optimized PBFT system when serving web content.
  • Real-World Relevance: A study of the Alexa Top 25 websites confirmed that over 90% of web requests are for static or rarely changing data, making them ideal candidates for Prophecy's fast-path optimization.
  • Scalability: By partitioning the history table across multiple sketchers using consistent hashing, the system demonstrates linear scalability.

Conclusion

Prophecy demonstrates that history-based validation can significantly reduce the cost of BFT for read-mostly workloads. By leveraging existing trust points in network infrastructure and accepting minor staleness through delay-once consistency, Prophecy makes Byzantine Fault Tolerance practical for high-throughput, real-world web services.

Summary updated

BibTeX
@inproceedings{sen2010prophecy,
  author = {Siddhartha Sen and Wyatt Lloyd and Michael J. Freedman},
  title = {{Prophecy: Using History for High-Throughput Fault Tolerance}},
  booktitle = {NSDI},
  year = {2010},
  url = {https://openreview.net/forum?id=WsbivM0GjN},
}
Figure