OSDI '06 Abstract
Pp. 177–190 of the Proceedings
HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault
Tolerance
James Cowling, Daniel Myers, and Barbara Liskov, MIT CSAIL; Rodrigo Rodrigues, INESC-ID and Instituto Superior Técnico; Liuba Shrira, Brandeis University
Abstract
There are currently two approaches to providing Byzantine-fault-tolerant state machine replication: a replica-based approach, e.g., BFT, that uses communication between replicas to agree on a proposed ordering of requests, and a quorum-based approach, such as Q/U, in which clients contact replicas directly to optimistically execute operations. Both approaches have shortcomings: the quadratic cost of inter-replica communication is unnecessary when there is no contention, and Q/U requires a large number of replicas and performs poorly under contention.
We present HQ, a hybrid Byzantine-fault-tolerant state machine
replication protocol that overcomes these problems. HQ employs a
lightweight quorum-based protocol when there is no contention, but
uses BFT to resolve contention when it arises. Furthermore,
HQ uses only 3f+1 replicas to tolerate f faults, providing optimal
resilience to node failures.
We implemented a prototype of HQ, and we compare its
performance to BFT and Q/U
analytically and experimentally. Additionally, in this
work we use a new implementation of BFT designed to scale as the
number of faults increases. Our results show that both HQ and our
new implementation of BFT scale as f increases;
additionally our hybrid approach of using BFT to handle contention
works well.
- View the full text of this paper in HTML and PDF. Listen to the presentation in MP3 format.
Until November 2007, you will need your USENIX membership identification in order to access the full papers.
The Proceedings are published as a collective work, © 2006 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
|
