A fault-scalable service can be configured to tolerate increasing
numbers of faults without significant decreases in performance.
The Query/Update (Q/U) protocol is a new tool
that enables construction of fault-scalable Byzantine fault-tolerant
services. The optimistic quorum-based nature of
the Q/U protocol allows it to provide better throughput
and fault-scalability than replicated state machines using
agreement-based protocols. A prototype service built using
the Q/U protocol outperforms the same service built using
a popular replicated state machine implementation at
all system sizes in experiments that permit an optimistic
execution. Moreover, the performance of the Q/U protocol
decreases by only 36% as the number of Byzantine faults tolerated
increases from one to five, whereas the performance
of the replicated state machine decreases by 83%.
FACULTY
Greg Ganger
Michael Reiter
GRAD STUDENTS
Michael Abd-El-Malek
Garth Goodson
Jay Wylie
This release contains a prototype implementing the Query/Update protocol. For more information on the protocol, see our SOSP 2005 paper. This prototype is the one used for that paper's experiments. While it is far from perfect, we are releasing it in the hope that it can foster further Q/U work and comparisons.
If you find this prototype useful, please let us know about it!
Fault-Scalable Byzantine Fault-Tolerant Services. Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter, Jay J. Wylie. SOSP’05, October 23-26, 2005, Brighton, United Kingdom.
Abstract / PDF [299K]
Correctness
of the Read/Conditional-Write and Query/Update Protocols.
Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael
K. Reiter, Jay J. Wylie. Carnegie Mellon University Parallel Data
Lab Technical Report CMU-PDL-05-107, September, 2005.
Abstract / PDF [392K]
We thank the members and companies of the PDL Consortium: Amazon, Bloomberg LP, Datadog, Google, Intel Corporation, Jane Street, LayerZero Research, Meta, Microsoft Research, Oracle Corporation, Oracle Cloud Infrastructure, Pure Storage, Salesforce, Samsung Semiconductor Inc., and Western Digital for their interest, insights, feedback, and support.