research-article

The next 700 BFT protocols

Authors:

Rachid Guerraoui,

Nikola Knežević,

Marko VukolićAuthors Info & Claims

EuroSys '10: Proceedings of the 5th European conference on Computer systems

Pages 363 - 376

https://doi.org/10.1145/1755913.1755950

Published: 13 April 2010 Publication History

Abstract

Modern Byzantine fault-tolerant state machine replication (BFT) protocols involve about 20,000 lines of challenging C++ code encompassing synchronization, networking and cryptography. They are notoriously difficult to develop, test and prove. We present a new abstraction to simplify these tasks. We treat a BFT protocol as a composition of instances of our abstraction. Each instance is developed and analyzed independently.

To illustrate our approach, we first show how our abstraction can be used to obtain the benefits of a state-of-the-art BFT protocol with much less pain. Namely, we develop AZyzzyva, a new protocol that mimics the behavior of Zyzzyva in best-case situations (for which Zyzzyva was optimized) using less than 24% of the actual code of Zyzzyva. To cover worst-case situations, our abstraction enables to use in AZyzzyva any existing BFT protocol, typically, a classical one like PBFT which has been tested and proved correct.

We then present Aliph, a new BFT protocol that outperforms previous BFT protocols both in terms of latency (by up to 30%) and throughput (by up to 360%). The development of Aliph required two new instances of our abstraction. Each instance contains less than 25% of the code needed to develop state-of-the-art BFT protocols.

References

[1]

M. Abd-El-Malek, G. Ganger, G. Goodson, M. Reiter, and J. Wylie. Fault-scalable Byzantine fault-tolerant services. In SOSP, 2005.

Digital Library

[2]

M. K. Aguilera, S. Frolund, V. Hadzilacos, S. L. Horn, and S. Toueg. Abortable and query-abortable objects and their efficient implementation. In PODC, 2007.

Digital Library

[3]

H. Attiya, R. Guerraoui, and P. Kouznetsov. Computing with reads and writes in the absence of step contention. In DISC, 2005.

Digital Library

[4]

R. Boichat, P. Dutta, S. Frölund, and R. Guerraoui. Deconstructing Paxos. SIGACT News in Distributed Computing, 34(1):47--67, 2003.

Digital Library

[5]

G. Bracha. An asynchronous {(n - 1)/3}-resilient consensus protocol. In PODC, 1984.

Digital Library

[6]

F. V. Brasileiro, F. Greve, A. Mostéfaoui, and M. Raynal. Consensus in one communication step. In PaCT, 2001.

Digital Library

[7]

M. Castro and B. Liskov. Practical Byzantine fault tolerance. In OSDI, 1999.

Digital Library

[8]

T. D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: an engineering perspective. In PODC, 2007.

Digital Library

[9]

W. Chen. Abortable consensus and its application to probabilistic atomic broadcast. Technical Report MSR-TR-2006-135, 2007.

[10]

B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz. Attested append-only memory: making adversaries stick to their word. In SOSP, 2007.

Digital Library

[11]

A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti. Making Byzantine fault tolerant systems tolerate Byzantine faults. In NSDI, 2009.

Digital Library

[12]

M. Correia, N. F. Neves, and P. Veríssimo. From consensus to atomic broadcast: Time-free Byzantine-resistant protocols without signatures. Comput. J., 49(1):82--96, 2006.

Digital Library

[13]

J. Cowling, D. Myers, B. Liskov, R. Rodrigues, and L. Shrira. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance. In OSDI, 2006.

Digital Library

[14]

R. De Prisco. On building blocks for distributed systems. PhD thesis, 2000. Massachusetts Institute of Technology.

Digital Library

[15]

D. Dobre and N. Suri. One-step consensus with zero-degradation. In DSN, 2006.

Digital Library

[16]

J. Gray. Notes on database operating systems. In Operating Systems -- An Advanced Course, number 66. 1978.

Digital Library

[17]

R. Guerraoui, V. Quéma, and M. Vukoli . The next 700 BFT protocols. Technical Report LPD-REPORT-2008-008, EPFL.

[18]

J. Hendricks, G. R. Ganger, and M. K. Reiter. Low-overhead byzantine fault-tolerant storage. In SOSP, 2007.

Digital Library

[19]

P. Jayanti. Adaptive and efficient abortable mutual exclusion. In PODC, 2003.

Digital Library

[20]

R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: speculative Byzantine fault tolerance. In SOSP, 2007.

Digital Library

[21]

R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: speculative Byzantine fault tolerance. Technical Report UTCS-TR-07-40, University of Texas at Austin, Austin, TX, USA, 2007.

Digital Library

[22]

K. Kursawe and V. Shoup. Optimistic asynchronous atomic broadcast. In ICALP, 2005.

Digital Library

[23]

L. Lamport. Specifying Systems, The TLA Language and Tools for Hardware and Software Engineers. Addison-Wesley, 2002.

Digital Library

[24]

L. Lamport. Lower bounds for asynchronous consensus. In FuDiCo, 2003.

Digital Library

[25]

F. Pedone. Boosting system performance with optimistic distributed protocols. Computer, 34(12):80--86, 2001.

Digital Library

[26]

R. Rodrigues, M. Castro, and B. Liskov. Base: using abstraction to improve fault tolerance. In SOSP, 2001.

Digital Library

[27]

B. Schroeder, A. Wierman, and M. Harchol-Balter. Open versus closed: a cautionary tale. In NSDI, pages 18--18, 2006.

Digital Library

[28]

A. Singh, T. Das, P. Maniatis, P. Druschel, and T. Roscoe. BFT protocols under fire. In NSDI, 2008.

Digital Library

[29]

R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. In OSDI, 2004.

Digital Library

Cited By

Diamantopoulos GBahsoon RTziritas NTheodoropoulos G(2024)SymBChainSim: A Novel Simulation System for Info-Symbiotic Blockchain ManagementACM Transactions on Modeling and Computer Simulation10.1145/3704917Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3704917
Chu DPanchapakesan RLaddad SKatahanas LLiu CShivakumar KCrooks NHellerstein JHoward H(2024)Optimizing Distributed Protocols with Query RewritesProceedings of the ACM on Management of Data10.1145/36392572:1(1-25)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639257
Amiri MAgrawal DEl Abbadi ALoo BBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Distributed Transaction Processing in Untrusted EnvironmentsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654684(570-579)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654684
Show More Cited By

Index Terms

The next 700 BFT protocols
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

The Next 700 BFT Protocols

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 ...
BFT-Bench: A Framework to Evaluate BFT Protocols
ICPE '16: Proceedings of the 7th ACM/SPEC on International Conference on Performance Engineering

Byzantine Fault Tolerance (BFT) has been extensively studied and numerous protocols and software prototypes have been proposed. However, most BFT prototypes have been evaluated in an ad-hoc setting, considering different fault types and fault injection ...
BFT-Bench: Towards a Practical Evaluation of Robustness and Effectiveness of BFT Protocols
Distributed Applications and Interoperable Systems
Abstract
Byzantine Fault Tolerance (BFT) is an interesting means to make computing systems resilient in presence of failures and attacks. That being said, designing and implementing BFT protocols is a hard and tedious task. This first comes from the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '10: Proceedings of the 5th European conference on Computer systems

April 2010

388 pages

ISBN:9781605585772

DOI:10.1145/1755913

General Chair:
Christine Morin
INRIA Rennes, France
,
Program Chair:
Gilles Muller
INRIA/LIP6, France

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EuroSys '10

Sponsor:

SIGOPS

EuroSys '10: Fifth EuroSys Conference 2010

April 13 - 16, 2010

Paris, France

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

157
Total Citations
View Citations
1,144
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)9

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Diamantopoulos GBahsoon RTziritas NTheodoropoulos G(2024)SymBChainSim: A Novel Simulation System for Info-Symbiotic Blockchain ManagementACM Transactions on Modeling and Computer Simulation10.1145/3704917Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3704917
Chu DPanchapakesan RLaddad SKatahanas LLiu CShivakumar KCrooks NHellerstein JHoward H(2024)Optimizing Distributed Protocols with Query RewritesProceedings of the ACM on Management of Data10.1145/36392572:1(1-25)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639257
Amiri MAgrawal DEl Abbadi ALoo BBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Distributed Transaction Processing in Untrusted EnvironmentsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654684(570-579)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654684
Hao RDai XDai W(2024)BitFT: An Understandable, Performant and Resource-Efficient Blockchain ConsensusIEEE Transactions on Sustainable Computing10.1109/TSUSC.2023.33414409:3(522-534)Online publication date: May-2024
https://doi.org/10.1109/TSUSC.2023.3341440
Zhang GPan FTijanic SJacobsen H(2024)PrestigeBFT: Revolutionizing View Changes in BFT Consensus Algorithms with Reputation Mechanisms2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00156(1930-1943)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00156
Mao CGolab WWong B(2024)Antipaxos: Taking Interactive Consistency to the Next LevelJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104839(104839)Online publication date: Jan-2024
https://doi.org/10.1016/j.jpdc.2024.104839
Zhu DGuan Y(2024)MBFTExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.125102257:COnline publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.125102
Ameri RMeybodi M(2024)An improved cellular goore game-based consensus protocol for blockchainCluster Computing10.1007/s10586-024-04300-127:5(6843-6868)Online publication date: 10-Mar-2024
https://doi.org/10.1007/s10586-024-04300-1
Albouy TFrey DRaynal MTaïani F(2024)Good-case early-stopping latency of synchronous byzantine reliable broadcast: the deterministic caseDistributed Computing10.1007/s00446-024-00464-637:2(121-143)Online publication date: 22-Mar-2024
https://doi.org/10.1007/s00446-024-00464-6
Ameri RMeybodi M(2024)Cognitive blockchain and its application to optimize performance in blockchain systemsTransactions on Emerging Telecommunications Technologies10.1002/ett.500935:7Online publication date: 19-Jun-2024
https://doi.org/10.1002/ett.5009
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents