Query/Update Protocol

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

People

Status

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.

Q/U Protocol v1.2
README file

Please send bug reports, experiences, and problems to mabdelmalek at cmu.edu. If you find this prototype useful, please let us know about it!

Publications

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]

Acknowledgements

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: American Power Conversion, Cisco Systems, EMC, Google, Hewlett-Packard Labs, Hitachi, IBM, Intel, LSI, Network Appliance, Oracle, Panasas, Seagate Technology, and Symantec for their interest, insights, feedback, and support.