HQ Replication: Properties and Optimizations
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 d...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Published: |
2007
|
| Online Access: | http://hdl.handle.net/1721.1/35888 |
| _version_ | 1811087972589633536 |
|---|---|
| author | Cowling, James Myers, Daniel Liskov, Barbara Rodrigues, Rodrigo Shrira, Liuba |
| author2 | Barbara Liskov |
| author_facet | Barbara Liskov Cowling, James Myers, Daniel Liskov, Barbara Rodrigues, Rodrigo Shrira, Liuba |
| author_sort | Cowling, James |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:54:45Z |
| id | mit-1721.1/35888 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:54:45Z |
| publishDate | 2007 |
| record_format | dspace |
| spelling | mit-1721.1/358882019-04-12T08:35:51Z HQ Replication: Properties and Optimizations Cowling, James Myers, Daniel Liskov, Barbara Rodrigues, Rodrigo Shrira, Liuba Barbara Liskov Programming Methodology 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. 2007-02-13T06:17:18Z 2007-02-13T06:17:18Z 2007-02-12 MIT-CSAIL-TR-2007-009 http://hdl.handle.net/1721.1/35888 Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 18 p. application/postscript application/pdf |
| spellingShingle | Cowling, James Myers, Daniel Liskov, Barbara Rodrigues, Rodrigo Shrira, Liuba HQ Replication: Properties and Optimizations |
| title | HQ Replication: Properties and Optimizations |
| title_full | HQ Replication: Properties and Optimizations |
| title_fullStr | HQ Replication: Properties and Optimizations |
| title_full_unstemmed | HQ Replication: Properties and Optimizations |
| title_short | HQ Replication: Properties and Optimizations |
| title_sort | hq replication properties and optimizations |
| url | http://hdl.handle.net/1721.1/35888 |
| work_keys_str_mv | AT cowlingjames hqreplicationpropertiesandoptimizations AT myersdaniel hqreplicationpropertiesandoptimizations AT liskovbarbara hqreplicationpropertiesandoptimizations AT rodriguesrodrigo hqreplicationpropertiesandoptimizations AT shriraliuba hqreplicationpropertiesandoptimizations |