Fault-Scalable Byzantine Fault-Tolerant Services

Proceedings SOSP’05, October 23–26, 2005, Brighton, United Kingdom.

Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson*, Michael K. Reiter, Jay J. Wylie

Parallel Data Laboratory
Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213

*Network Appliance


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

KEYWORDS: Fault-scalability, Byzantine fault-tolerance, quorums, services, replicated state machines





© 2017. Last updated 15 March, 2012