Practical byzantine fault tolerance and proactive recovery
Abstract
Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2% faster to 24% slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Using PBFT as a consensus protocol, a blockchain network of N nodes can withstand a number of failed nodes, f, where f=(N−1)/3.
“Using PBFT as a consensus protocol, a blockchain network of N nodes can withstand a number of failed nodes, f, where f=(N−1)/3.”
From Tamper-Resistant Mobile Health Using Blockchain Technology. (2017) · cites this paper as [33]
PBFT ensures that a minimum of 2×f + 1 (that is 3) nodes reach consensus on the order of transactions before appending them to the shared ledger.
“In other words, PBFT ensures that a minimum of 2×f + 1 (that is 3) nodes reach consensus on the order of transactions before appending them to the shared ledger.”
From Tamper-Resistant Mobile Health Using Blockchain Technology. (2017) · cites this paper as [33]
Cites
A Digital Signature Based on a Conventional Encryption Function
Merkle, R. C. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2_32 · Cited by 1,998 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Hyperledger fabric: a distributed operating system for permissioned blockchains
Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., De Caro, A., Enyeart, D., Ferris, C., Laventman, G., Manevich, Y., et al. (2018) · Proceedings of the Thirteenth EuroSys Conference · doi:10.1145/3190508.3190538 · Cited by 3,654 · see citing works
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., & Zeldovich, N. (2017) · Proceedings of the 26th Symposium on Operating Systems Principles · doi:10.1145/3132747.3132757 · Cited by 1,499 · see citing works
A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection
Li, Q., Wen, Z., Wu, Z., Hu, S., Wang, N., Li, Y., Liu, X., & He, B. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3124599 · Cited by 1,407 · see citing works
A Survey on Security and Privacy Issues of Bitcoin
Conti, M., Sandeep Kumar, E., Lal, C., & Ruj, S. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2842460 · Cited by 1,116 · see citing works
The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication
Vukolić, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-39028-4_9 · Cited by 1,051 · see citing works
Healthcare blockchain system using smart contracts for secure automated remote patient monitoring
Griggs, K. N., Ossipova, O., Kohlios, C. P., Baccarini, A. N., Howson, E. A., & Hayajneh, T. (2018) · Journal of Medical Systems · doi:10.1007/s10916-018-0982-x · Cited by 926 · see citing works
Pinocchio: Nearly Practical Verifiable Computation
Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.47 · Cited by 864 · see citing works
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2020) · IEEE Access · doi:10.1109/access.2020.2968985 · Cited by 607 · see citing works
Comparative analysis of blockchain consensus algorithms
Bach, L. M., Mihaljevic, B., & Zagar, M. (2018) · 2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO) · doi:10.23919/mipro.2018.8400278 · Cited by 584 · see citing works
Blockchain's adoption in iot: the challenges, and a way forward
Makhdoom, I., Abolhasan, M., Abbas, H., & Ni, W. (2019) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.10.019 · Cited by 501 · see citing works
From blockchain consensus back to byzantine consensus
Gramoli, V. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2017.09.023 · Cited by 314 · see citing works
Security, Performance, and Applications of Smart Contracts: A Systematic Survey
Rouhani, S., & Deters, R. (2019) · IEEE Access · doi:10.1109/access.2019.2911031 · Cited by 309 · see citing works
Tamper-Resistant Mobile Health Using Blockchain Technology.
Ichikawa, D., Kashiyama, M., & Ueno, T. (2017) · JMIR mHealth and uHealth · doi:10.2196/mhealth.7938 · Cited by 298 · see citing works
“At that time, each VP followed the consensus algorithm, which was called the Practical Byzantine Fault Tolerance (PBFT) algorithm [33,34].”
MethodA Survey on Digital Twin for Industrial Internet of Things: Applications, Technologies and Tools
Xu, H., Wu, J., Pan, Q., Guan, X., & Guizani, M. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2023.3297395 · Cited by 304 · see citing works
A review of secure and privacy-preserving medical data sharing
Jin, H., Luo, Y., Li, P., & Mathew, J. (2019) · IEEE Access · doi:10.1109/access.2019.2916503 · Cited by 293 · see citing works
Kiktenko, E. O., Pozhar, N. O., Anufriev, M. N., Trushechkin, A. S., Yunusov, R. R., Kurochkin, Y. V., Lvovsky, A. I., & Fedorov, A. K. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aabc6b · Cited by 264 · see citing works
EACMS: Emergency Access Control Management System for Personal Health Record Based on Blockchain
Rajput, A. R., Li, Q., Taleby Ahvanooey, M., & Masood, I. (2019) · IEEE Access · doi:10.1109/access.2019.2917976 · Cited by 166 · see citing works
A Survey of Self-Sovereign Identity Ecosystem
Soltani, R., Nguyen, U. T., & An, A. (2021) · Security and Communication Networks · doi:10.1155/2021/8873429 · Cited by 131 · see citing works
A New Lattice-Based Signature Scheme in Post-Quantum Blockchain Network
Li, C.-Y., Chen, X.-B., Chen, Y.-L., Hou, Y.-Y., & Li, J. (2019) · IEEE Access · doi:10.1109/access.2018.2886554 · Cited by 126 · see citing works
Reviewing Federated Machine Learning and Its Use in Diseases Prediction
Moshawrab, M., Adda, M., Bouzouane, A., Ibrahim, H., & Raad, A. (2023) · Sensors · doi:10.3390/s23042112 · Cited by 114 · see citing works
Blockchain-based distributed software-defined vehicular networks: a dueling deep q-learning approach
Zhang, D., Yu, F. R., & Yang, R. (2019) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2019.2944399 · Cited by 96 · see citing works
A secure and auditable logging infrastructure based on a permissioned blockchain
Putz, B., Menges, F., & Pernul, G. (2019) · Computers & Security · doi:10.1016/j.cose.2019.101602 · Cited by 77 · see citing works
Survivable zero trust for cloud computing environments
Ferretti, L., Magnanini, F., Andreolini, M., & Colajanni, M. (2021) · Computers & Security · doi:10.1016/j.cose.2021.102419 · Cited by 69 · see citing works
BlockSee: Blockchain for IoT Video Surveillance in Smart Cities
Gallo, P., Pongnumkul, S., & Quoc Nguyen, U. (2018) · 2018 IEEE International Conference on Environment and Electrical Engineering and 2018 IEEE Industrial and Commercial Power Systems Europe (EEEIC / I&CPS Europe) · doi:10.1109/eeeic.2018.8493895 · Cited by 55 · see citing works
“Combating deepfakes: multi-LSTM and blockchain as proof of authenticity for digital media,”
Ki Chan, C. C., Kumar, V., Delaney, S., & Gochoo, M. (2020) · 2020 IEEE / ITU International Conference on Artificial Intelligence for Good (AI4G) · doi:10.1109/ai4g50087.2020.9311067 · Cited by 48 · see citing works
A Comparative Survey on Blockchain Based Self Sovereign Identity System
Kaneriya, J., & Patel, H. (2020) · 2020 3rd International Conference on Intelligent Sustainable Systems (ICISS) · doi:10.1109/iciss49785.2020.9315899 · Cited by 31 · see citing works
Hossain, M. J., Wadud, M. A. H., Rahman, A., Ferdous, J., Alam, M. S., Amir - Ul - Haque Bhuiyan, T. M., & Mridha, M. F. (2021) · 2021 International Conference on Science & Contemporary Technologies (ICSCT) · doi:10.1109/icsct53883.2021.9642537 · Cited by 18 · see citing works
Qualified eID Derivation Into a Distributed Ledger Based IdM System
Abraham, A., Theuermann, K., & Kirchengast, E. (2018) · 2018 17th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/ 12th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE) · doi:10.1109/trustcom/bigdatase.2018.00195 · Cited by 18 · see citing works
Xu, C., Zhang, P., Yu, H., & Li, Y. (2025) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2025.3544478 · Cited by 16 · see citing works
“To guarantee blockchain consensus and reduce trustworthy edge computing delay, we further propose the dynamic consensus waiting mechanism based on BFT since the failure of the minority nodes would not affect the blockchain consensus [26].”
- Authors
- Castro, M., & Liskov, B.
- Affiliations
- Microsoft (United States) (US)
- Massachusetts Institute of Technology (US)
- ORCID
- Castro, Miguel
- Venue
- ACM Transactions on Computer Systems
- Published
- 2002-11
- Volume
- 20
- Issue
- 4
- Pages
- 398-461
- ISSN
- 0734-2071 (ISSN-L)
- 1557-7333
- OpenAlex
- W2114579022
- Cited by
- 2,475
- References
- 1
- Citations by year
- 2026: 65 · 2025: 147 · 2024: 167 · 2023: 196 · 2022: 204 · 2021: 276 · 2020: 219 · 2019: 183 · 2018: 158 · 2017: 72 · 2016: 51 · 2015: 40 · 2014: 62 · 2013: 75 · 2012: 83
- FWCI
- 31.74
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- ACM Transactions on Computer Systems (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed systems and fault tolerance
- Physical Sciences › Computer Science › Computer Networks and Communications › Software System Performance and Reliability
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Database Systems and Queries
- Keywords
- Byzantine fault tolerance, replication algorithms, proactive recovery, highly available systems, message authentication, symmetric encryption, asynchronous distributed systems
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
