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. |
Year | Venue | Keywords |
---|---|---|
2006 | OSDI | state machine |
Field | DocType | Citations |
Replica,State machine replication,Computer science,Quadratic cost,Byzantine fault tolerance,Real-time computing,Zyzzyva,Distributed computing | Conference | 117 |
PageRank | References | Authors |
4.64 | 14 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
James Cowling | 1 | 250 | 9.36 |
Daniel Myers | 2 | 145 | 6.93 |
Barbara Liskov | 3 | 6025 | 1219.69 |
Rodrigo Rodrigues | 4 | 352 | 19.46 |
Liuba Shrira | 5 | 1141 | 178.23 |