Q/U Protocol Software

Contact: Greg Ganger

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!



We thank the CyLab Corporate Partners for their support and participation.

This work is supported in part by Army Research Office grant number DAAD19-02-1-0389 and by Air Force Research Laboratory grant number FA8750-04-01-0238.

We thank the members and companies of the PDL Consortium: Alibaba Group, Amazon, Datrium, Facebook, Google, Hewlett Packard Enterprise, Hitachi Ltd., Intel Corporation, IBM, Micron, Microsoft Research, NetApp, Inc., Oracle Corporation, Salesforce, Samsung Semiconductor Inc., Seagate Technology, and Two Sigma for their interest, insights, feedback, and support.




© 2020. Legal Info.
Last updated 15 January, 2019