HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance

@inproceedings{citeulike:1111038, 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.}, author = {Cowling, James and Myers, Daniel and Liskov, Barbara and Rodrigues, Rodrigo and Shrira, Liuba }, booktitle = {Operating Systems Design \& Implementation}, citeulike-article-id = {1111038}, keywords = {algorithm, distributed, fault, protocol, quorum, replication, tolerance}, month = {November}, pages = {177--190}, posted-at = {2007-02-18 05:40:40}, priority = {2}, publisher = {Usenix}, title = {HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance}, url = {http://people.csail.mit.edu/cowling/hq/hq-osdi06.pdf}, year = {2006} }

TY - CONF ID - citeulike:1111038 L3 - citeulike-article-id:1111038 TI - HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance T2 - Operating Systems Design & Implementation SP - 177 EP - 190 PB - Usenix N2 - 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. KW - algorithm KW - distributed KW - fault KW - protocol KW - quorum KW - replication KW - tolerance AU - Cowling, James AU - Myers, Daniel AU - Liskov, Barbara AU - Rodrigues, Rodrigo AU - Shrira, Liuba PY - 2006/11// UR - http://people.csail.mit.edu/cowling/hq/hq-osdi06.pdf ER -