Article

Beyond one-third faulty replicas in byzantine fault tolerant systems

Authors:

David MaziéresAuthors Info & Claims

NSDI'07: Proceedings of the 4th USENIX conference on Networked systems design & implementation

Page 10

Published: 11 April 2007 Publication History

Abstract

Byzantine fault tolerant systems behave correctly when no more than f out of 3f + 1 replicas fail. When there are more than f failures, traditional BFT protocols make no guarantees whatsoever. Malicious replicas can make clients accept arbitrary results, and the system behavior is totally unspecified. However, there is a large spectrum between complete correctness and arbitrary failure that traditional BFT systems ignore. This paper argues that we can and should bound the system behavior beyond f failures.

We present BFT2F, an extension to the well-known Castro-Liskov PBFT algorithm [6], to explore the design space beyond f failures. Specifically, BFT2F has the same liveness and consistency guarantees as PBFT when no more than f replicas fail; with more than f but no more than 2f failures, BFT2F prohibits malicious servers from making up operations that clients have never issued and restricts malicious servers to only certain kinds of consistency violations. Evaluations of a prototype implementation show that the additional guarantees of BFT2F come at the cost of only a slight performance degradation compared to PBFT.

References

[1]

Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter, and Jay J. Wylie. Fault-scalable Byzantine fault-tolerant services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles, pages 59-74, Brighton, United Kingdom, October 2005. ACM.

Digital Library

[2]

Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. FARSITE: Federated, available, and reliable storage for an incompletely trusted environment. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation, pages 1-14, December 2002.

Digital Library

[3]

Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl Porth. BAR fault tolerance for cooperative services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles, pages 45-58, Brighton, United Kingdom, October 2005. ACM.

Digital Library

[4]

Lorenzo Alvisi, Dahlia Malkhi, Evelyn Pierce, Michael K. Reiter, and Rebecca N. Wright. Dynamic Byzantine quorum systems. In Proceedings of the the International Conference on Dependable Systems and Networks (FTCS 30 and DCCA 8), pages 283-292, June 2000.

Digital Library

[5]

Christian Cachin and Jonathan A. Poritz. Secure intrusion-tolerant replication on the internet. In Proceedings of the 2002 International Conference on Dependable Systems and Networks, pages 167-176, 2002.

Digital Library

[6]

Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, pages 173-186, New Orleans, LA, February 1999.

Digital Library

[7]

Miguel Castro and Barbara Liskov. Proactive recovery in a Byzantine-fault-tolerant system. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, pages 273-288, San Diego, CA, October 2000.

Digital Library

[8]

James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, pages 177-190, Seattle, WA, November 2006.

Digital Library

[9]

Maurice P. Herlihy and Jeannette M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages Systems, 12(3):463-492, 1990.

Digital Library

[10]

Kim Potter Kihlstrom, L. E. Moser, and P. M. Melliar-Smith. The SecureRing group communication system. ACM Transactions on Information and System Security, 4(4):371-406, 2001.

Digital Library

[11]

Jinyuan Li, Maxwell Krohn, David Mazières, and Dennis Shasha. Secure untrusted data repository (SUNDR). In Proceedings of the 6th Symposium on Operating Systems Design and Implementation, pages 121-136, December 2004.

Digital Library

[12]

Dahlia Malkhi and Michael Reiter. Byzantine quorum system. In Proceedings of the ACM Symposium on Theory of Computing, pages 569-578, El Paso, TX, May 1997.

Digital Library

[13]

Dahlia Malkhi and Michael Reiter. Secure and scalable replication in Phalanx. In Proceedings of the 7th IEEE Symposium on Reliable Distributed Systems, pages 51-58, October 1998.

Digital Library

[14]

Dahlia Malkhi, Michael K. Reiter, Daniela Tulone, and Elisha Ziskind. Persistent objects in the Fleet system. In Proceedings of the 2nd DARPA Information Survivability Conference and Exposition (DISCEX II), 2001.

[15]

Petros Maniatis and Mary Baker. Secure history preservation through timeline entanglement. In Proceedings of the 11th USENIX Security Symposium, San Francisco, CA, August 2002.

Digital Library

[16]

David Mazières and Dennis Shasha. Building secure file systems out of Byzantine storage. In Proceedings of the 21st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 108-117, July 2002. The full version is available as NYU computer science department technical report TR2002- 826, May 2002.

Digital Library

[17]

Michael Reiter and Li Gong. Securing causal relationships in distributed systems. The Computer Journal, 38(8):633-642, 1995.

[18]

Michael K. Reiter. The Rampart toolkit for building highintegrity services. Lecture Notes in Computer Science 938, pages 99-110, 1994.

Digital Library

[19]

Sean Rhea, Patrick Eaton, and Dennis Geels. Pond: The OceanStore prototype. In 2nd USENIX conference on File and Storage Technologies (FAST '03), San Francisco, CA, April 2003.

Digital Library

[20]

Rodrigo Rodrigues, Miguel Castro, and Barbara Liskov. BASE: Using abstraction to improve fault tolerance. In Proceedings of the 18th ACM Symposium on Operating Systems Principles, pages 15-28, Chateau Lake Louise, Banff, Canada, October 2001. ACM.

Digital Library

[21]

Fred B. Schneider. Implementing fault-tolerant services using the state machine approach. ACM Computing Surveys, 22(4):299-319, December 1990.

Digital Library

[22]

Dale Skeen. Nonblocking commit protocols. In Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, MI, April 1981.

Digital Library

[23]

Sean W. Smith and J. D. Tygar. Security and privacy for partial order time. In Proceedings of the ISCA International Conference on Parallel and Distributed Computing Systems, pages 70-79, Las Vegas, NV, October 1994.

[24]

Jian Yin, Jean-Philippe Martin, Arun Venkataramani, Lorenzo Alvisi, and Mike Dahlin. Separating agreement from execution for Byzantine fault tolerant services. In Proceedings of the 19th ACM Symposium on Operating Systems Principles, pages 253- 267, Bolton Landing, NY, October 2003. ACM.

Digital Library

[25]

Lidong Zhou, Fred B. Schneider, and Robbert van Renesse. COCA: A secure distributed on-line certification authority. ACM Transactions on Computer Systems, 20(4):329-368, November 2002.

Digital Library

Cited By

Moore MKuppusamy TCappos J(2023)Artemis: Defanging Software Supply Chain Attacks in Multi-repository Update SystemsProceedings of the 39th Annual Computer Security Applications Conference10.1145/3627106.3627129(83-97)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3627106.3627129
Messadi IBecker MBleeke KJehl LMokhtar SKapitza RBellavista PZhang KGherbi ABagchi SPatiño MDi Modica GGascon-Samson J(2022)SplitBFTProceedings of the 23rd ACM/IFIP International Middleware Conference10.1145/3528535.3531516(56-68)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3528535.3531516
Gandhi NRoth ESandler BHaeberlen APhan LBarbalace ABhatotia PAlvisi LCadar C(2021)REBOUNDProceedings of the Sixteenth European Conference on Computer Systems10.1145/3447786.3456257(523-539)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1145/3447786.3456257
Show More Cited By

Beyond one-third faulty replicas in byzantine fault tolerant systems
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Making Byzantine fault tolerant systems tolerate Byzantine faults
NSDI'09: Proceedings of the 6th USENIX symposium on Networked systems design and implementation

This paper argues for a new approach to building Byzantine fault tolerant replication systems. We observe that although recently developed BFT state machine replication protocols are quite fast, they don't tolerate Byzantine faults very well: a single ...
Making CRDTs Byzantine fault tolerant
PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data

It is often claimed that Conflict-free Replicated Data Types (CRDTs) ensure consistency of replicated data in peer-to-peer systems. However, peer-to-peer systems usually consist of untrusted nodes that may deviate from the specified protocol (i.e. ...
Byzantine Fault-Tolerant MapReduce: Faults are Not Just Crashes
CLOUDCOM '11: Proceedings of the 2011 IEEE Third International Conference on Cloud Computing Technology and Science

MapReduce is often used to run critical jobs such as scientific data analysis. However, evidence in the literature shows that arbitrary faults do occur and can probably corrupt the results of MapReduce jobs. MapReduce runtimes like Hadoop tolerate crash ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

NSDI'07: Proceedings of the 4th USENIX conference on Networked systems design & implementation

April 2007

27 pages

Sponsors

VMware
Google Inc.
Microsoft Research: Microsoft Research
Intel: Intel
CISCO

Publisher

USENIX Association

United States

Publication History

Published: 11 April 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Moore MKuppusamy TCappos J(2023)Artemis: Defanging Software Supply Chain Attacks in Multi-repository Update SystemsProceedings of the 39th Annual Computer Security Applications Conference10.1145/3627106.3627129(83-97)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3627106.3627129
Messadi IBecker MBleeke KJehl LMokhtar SKapitza RBellavista PZhang KGherbi ABagchi SPatiño MDi Modica GGascon-Samson J(2022)SplitBFTProceedings of the 23rd ACM/IFIP International Middleware Conference10.1145/3528535.3531516(56-68)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3528535.3531516
Gandhi NRoth ESandler BHaeberlen APhan LBarbalace ABhatotia PAlvisi LCadar C(2021)REBOUNDProceedings of the Sixteenth European Conference on Computer Systems10.1145/3447786.3456257(523-539)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1145/3447786.3456257
Cachin COhrimenko O(2018)Verifying the consistency of remote untrusted services with conflict-free operationsInformation and Computation10.1016/j.ic.2018.03.004260:C(72-88)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.ic.2018.03.004
Gilad YHemo RMicali SVlachos GZeldovich N(2017)AlgorandProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132757(51-68)Online publication date: 14-Oct-2017
https://dl.acm.org/doi/10.1145/3132747.3132757
Viotti PVukolić M(2016)Consistency in Non-Transactional Distributed Storage SystemsACM Computing Surveys10.1145/292696549:1(1-34)Online publication date: 29-Jun-2016
https://dl.acm.org/doi/10.1145/2926965
Porto DLeitão JLi CClement AKate AJunqueira FRodrigues RRéveillère LHarris THerlihy M(2015)Visigoth fault toleranceProceedings of the Tenth European Conference on Computer Systems10.1145/2741948.2741979(1-14)Online publication date: 17-Apr-2015
https://dl.acm.org/doi/10.1145/2741948.2741979
Davoli AMei AShapiro M(2014)TritonProceedings of the First Workshop on Principles and Practice of Eventual Consistency10.1145/2596631.2596644(1-7)Online publication date: 13-Apr-2014
https://dl.acm.org/doi/10.1145/2596631.2596644
Tate SVishwanathan REverhart LBertino ESandhu RBauer LPark J(2013)Multi-user dynamic proofs of data possession using trusted hardwareProceedings of the third ACM conference on Data and application security and privacy10.1145/2435349.2435400(353-364)Online publication date: 18-Feb-2013
https://dl.acm.org/doi/10.1145/2435349.2435400
Mahajan PSetty SLee SClement AAlvisi LDahlin MWalfish M(2011)DepotACM Transactions on Computer Systems10.1145/2063509.206351229:4(1-38)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2063509.2063512
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents