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.

Please send bug reports, experiences, and problems to mabdelmalek at cmu.edu. 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: Actifio, American Power Conversion, EMC Corporation, Facebook, Fusion-io,Google, Hewlett-Packard Labs, Hitachi, Huawei Technologies Co., Intel Corporation, Microsoft Research, NEC Laboratories, NetApp, Inc., Oracle Corporation, Panasas, Samsung Information Systems America, Seagate Technology, Symantec Corporation, VMware, Inc., and Western Digital for their interest, insights, feedback, and support.




© 2014. Last updated 14 March, 2012