“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.
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}
}
Programming Methodology Group