Q/U Protocol Software

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%.



Greg Ganger
Michael Reiter


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, Google, Hewlett Packard Enterprise, Hitachi Ltd., Intel Corporation, IBM, Meta, Microsoft Research, NetApp, Inc., Oracle Corporation, Pure Storage, Salesforce, Samsung Semiconductor Inc., Seagate Technology, Two Sigma, and Western Digital for their interest, insights, feedback, and support.