HQ Replication: Properties and Optimizations

Download: pdf.

“HQ Replication: Properties and Optimizations” by James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. MIT Technical Report MIT-CSAIL-TR-2007-009, (Cambridge, MA), Feb. 2007.

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.

Download: pdf.

BibTeX entry:

@techreport{HQ-TR,
   author = {James Cowling and Daniel Myers and Barbara Liskov and Rodrigo
	Rodrigues and Liuba Shrira},
   title = {HQ Replication: Properties and Optimizations},
   institution = {MIT},
   type = {Technical Report},
   number = {MIT-CSAIL-TR-2007-009},
   address = {Cambridge, MA},
   month = feb,
   year = {2007}
}