HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance
Download:
pdf,
html.
``HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance''
by
James Cowling,
Daniel Myers,
Barbara Liskov,
Rodrigo Rodrigues,
and
Liuba Shrira.
In Proceedings of the Seventh Symposium on Operating Systems Design
and Implementations (OSDI),
(Seattle, Washington), Nov. 2006.
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.
BibTeX entry:
@inproceedings{HQ-OSDI,
author = {James Cowling and Daniel Myers and Barbara Liskov and Rodrigo
Rodrigues and Liuba Shrira},
title = {HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault
Tolerance},
booktitle = {Proceedings of the Seventh Symposium on Operating Systems
Design and Implementations (OSDI)},
address = {Seattle, Washington},
month = nov,
year = {2006}
}