CoChat

The Next 700 BFT Protocols

Open access
Aublin, Pierre-Louis, Guerraoui, Rachid, Knežević, Nikola, Quéma, Vivien, Vukolić, Marko · 2015 · ACM Transactions on Computer Systems
Cited by 135

The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.

Abstract

We present Abstract (ABortable STate mAChine replicaTion), a new abstraction for designing and reconfiguring generalized replicated state machines that are, unlike traditional state machines, allowed to abort executing a client’s request if “something goes wrong.” Abstract can be used to considerably simplify the incremental development of efficient Byzantine fault-tolerant state machine replication ( BFT ) protocols that are notorious for being difficult to develop. In short, we treat a BFT protocol as a composition of Abstract instances. Each instance is developed and analyzed independently and optimized for specific system conditions. We illustrate the power of Abstract through several interesting examples. We first show how Abstract can yield benefits of a state-of-the-art BFT protocol in a less painful and error-prone manner. Namely, we develop AZyzzyva , a new protocol that mimics the celebrated best-case behavior of Zyzzyva using less than 35% of the Zyzzyva code. To cover worst-case situations, our abstraction enables one to use in AZyzzyva any existing BFT protocol. We then present Aliph , a new BFT protocol that outperforms previous BFT protocols in terms of both latency (by up to 360%) and throughput (by up to 30%). Finally, we present R-Aliph , an implementation of Aliph that is robust , that is, whose performance degrades gracefully in the presence of Byzantine replicas and Byzantine clients.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/2658994

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 2 references

Research works printed but not linked: 33

  1. 10.1145/1095810.1095817 · DOI · Paper page
  2. 10.1145/1281100.1281107 · doi:10.1145/1281100.1281107
  3. 10.1109/TDSC.2010.70 · DOI · Paper page
  4. 10.1007/11561927_11 · doi:10.1007/11561927_11
  5. 10.1145/637437.637447 · DOI
  6. 10.5555/645768.667612 · doi:10.5555/645768.667612
  7. 10.1145/859716.859718 · DOI
  8. 10.1145/1281100.1281103 · DOI · Paper page
  9. Allen Clement , Edmund Wong , Lorenzo Alvisi , Mike Dahlin , and Mirco Marchetti . 2009 . Making Byzantine fault tolerant systems tolerate Byzantine faults . In Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI’09) . Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. 2009. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI’09).
  10. James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , and Liuba Shrira . 2006 . HQ replication: A hybrid quorum protocol for Byzantine fault tolerance . In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI’06) . USENIX Association. http://portal.acm.org/citation.cfm?id=1298455.1298473. James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. 2006. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance. In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI’06). USENIX Association. http://portal.acm.org/citation.cfm?id=1298455.1298473.
  11. 10.1109/DSN.2006.55 · DOI
  12. 10.1145/42282.42283 · DOI · Paper page
  13. 10.1145/3149.214121 · DOI · Paper page
  14. 10.1109/DSN.2011.5958251 · DOI
  15. 10.1109/TDSC.2007.70208 · DOI
  16. Jim Gray . 1978. Notes on data base operating systems . In Operating Systems—An Advanced Course . Springer-Verlag , 393--481. http://dl.acm.org/citation.cfm?id=647433.723863 Jim Gray. 1978. Notes on data base operating systems. In Operating Systems—An Advanced Course. Springer-Verlag, 393--481. http://dl.acm.org/citation.cfm?id=647433.723863
  17. 10.1145/1755913.1755950 · DOI · Paper page
  18. 10.1145/1294261.1294269 · DOI
  19. 10.1145/78969.78972 · DOI · Paper page
  20. 10.1145/872035.872079 · doi:10.1145/872035.872079
  21. 10.1145/2168836.2168866 · DOI · Paper page
  22. 10.1145/1658357.1658358 · DOI · Paper page
  23. 10.1007/3-540-37795-6_4 · DOI
  24. 10.1007/978-3-642-03466-4_2 · DOI
  25. 10.1145/1753171.1753191 · DOI
  26. 10.1109/2.970581 · doi:10.1109/2.970581
  27. Bianca Schroeder , Adam Wierman , and Mor Harchol-Balter . 2006 . Open versus closed: A cautionary tale . In Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI). 18--18 . Bianca Schroeder, Adam Wierman, and Mor Harchol-Balter. 2006. Open versus closed: A cautionary tale. In Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI). 18--18.
  28. Atul Singh , Tathagata Das , Petros Maniatis , Peter Druschel , and Timothy Roscoe . 2008 . BFT protocols under fire . In Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI’08) . USENIX Association. Atul Singh, Tathagata Das, Petros Maniatis, Peter Druschel, and Timothy Roscoe. 2008. BFT protocols under fire. In Proceedings of the Symposium on Networked Systems Design and Implementation (NSDI’08). USENIX Association.
  29. 10.1145/800222.806744 · DOI
  30. Robbert van Renesse and Rachid Guerraoui . 2010. Replication techniques for availability . In Replication, B. Charron-Bost, F. Pedone, and A. Schiper (Eds.). Springer-Verlag , 19--40. http://dl.acm.org/citation.cfm?id=2172338.2172340" Robbert van Renesse and Rachid Guerraoui. 2010. Replication techniques for availability. In Replication, B. Charron-Bost, F. Pedone, and A. Schiper (Eds.). Springer-Verlag, 19--40. http://dl.acm.org/citation.cfm?id=2172338.2172340"
  31. Robbert van Renesse and Fred B. Schneider . 2004. Chain replication for supporting high throughput and availability . In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI’04) . Robbert van Renesse and Fred B. Schneider. 2004. Chain replication for supporting high throughput and availability. In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI’04).
  32. 10.1109/SRDS.2009.36 · DOI · Paper page
  33. 10.1109/TC.2011.221 · DOI · Paper page

Cited by

Metadata

Authors
Aublin, P.-L., Guerraoui, R., Knežević, N., Quéma, V., & Vukolić, M.
Venue
ACM Transactions on Computer Systems
Published
2015-01-20
Volume
32
Issue
4
Pages
1-45
ISSN
  • 0734-2071 (ISSN-L)
  • 1557-7333
OpenAlex
W2124037649
Cited by
135
References
2
FWCI
12.28
Type
journal article
Language
en
Open access
green

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.