The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
Efficient Byzantine Fault-Tolerance
Abstract
We present two asynchronous Byzantine fault-tolerant state machine replication (BFT) algorithms, which improve previous algorithms in terms of several metrics. First, they require only 2f+1 replicas, instead of the usual 3f+1. Second, the trusted service in which this reduction of replicas is based is quite simple, making a verified implementation straightforward (and even feasible using commercial trusted hardware). Third, in nice executions the two algorithms run in the minimum number of communication steps for nonspeculative and speculative algorithms, respectively, four and three steps. Besides the obvious benefits in terms of cost, resilience and management complexity-fewer replicas to tolerate a certain number of faults-our algorithms are simpler than previous ones, being closer to crash fault-tolerant replication algorithms. The performance evaluation shows that, even with the trusted component access overhead, they can have better throughput than Castro and Liskov's PBFT, and better latency in networks with nonnegligible communication delays.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
The Byzantine generals problem
Lamport, L., Shostak, R., & Pease, M. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357172.357176 · Cited by 6,023
Xen and the art of virtualization
Barham, P., Dragovic, B., Fraser, K., Hand, S., Harris, T., Ho, A., Neugebauer, R., Pratt, I., & Warfield, A. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945462 · Cited by 5,915
Practical byzantine fault tolerance and proactive recovery
Castro, M., & Liskov, B. (2002) · ACM Transactions on Computer Systems · doi:10.1145/571637.571640 · Cited by 2,475
Implementing fault-tolerant services using the state machine approach: a tutorial
Schneider, F. B. (1990) · ACM Computing Surveys · doi:10.1145/98163.98167 · Cited by 2,387
Reaching Agreement in the Presence of Faults
Pease, M., Shostak, R., & Lamport, L. (1980) · Journal of the ACM · doi:10.1145/322186.322188 · Cited by 2,359
Xen and the art of virtualization
Barham, P., Dragovic, B., Fraser, K., Hand, S., Harris, T., Ho, A., Neugebauer, R., Pratt, I., & Warfield, A. (2003) · Proceedings of the nineteenth ACM symposium on Operating systems principles · doi:10.1145/945445.945462 · Cited by 2,107
HMAC: Keyed-Hashing for Message Authentication
Krawczyk, H., Bellare, M., & Canetti, R. (1997) · doi:10.17487/rfc2104 · Cited by 2,031
Consensus in the presence of partial synchrony
Dwork, C., Lynch, N., & Stockmeyer, L. (1988) · Journal of the ACM · doi:10.1145/42282.42283 · Cited by 1,909
Xen and the art of virtualization
Barham, P., Dragovic, B., Fraser, K., Hand, S., Harris, T., Ho, A., & Neugebauer, R. (2003) · Proceedings of the nineteenth ACM symposium on Operating systems principles - SOSP '03 · doi:10.1145/945461.945462 · Cited by 1,552
Terra: a virtual machine-based platform for trusted computing
Garfinkel, T., Pfaff, B., Chow, J., Rosenblum, M., & Boneh, D. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945464 · Cited by 887
SEDA: an architecture for well-conditioned, scalable internet services
Welsh, M., Culler, D., & Brewer, E. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502057 · Cited by 834
Farsite: federated, available, and reliable storage for an incompletely trusted environment
Adya, A., Bolosky, W. J., Castro, M., Cermak, G., Chaiken, R., Douceur, J. R., Howell, J., Lorch, J. R., Theimer, M., & Wattenhofer, R. P. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844130 · Cited by 780
Flicker: an execution infrastructure for tcb minimization
McCune, J. M., Parno, B. J., Perrig, A., Reiter, M. K., & Isozaki, H. (2008) · Proceedings of the 3rd ACM SIGOPS/EuroSys European Conference on Computer Systems 2008 · doi:10.1145/1352592.1352625 · Cited by 640
Zyzzyva: speculative byzantine fault tolerance
Kotla, R., Alvisi, L., Dahlin, M., Clement, A., & Wong, E. (2007) · Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles · doi:10.1145/1294261.1294267 · Cited by 638
vTPM: virtualizing the trusted platform module
Berger, S., Cáceres, R., Goldman, K., Perez, R., Sailer, R., & van Doorn, L. (2006) · Cited by 527
Terra: a virtual machine-based platform for trusted computing
Garfinkel, T., Pfaff, B., Chow, J., Rosenblum, M., & Boneh, D. (2003) · Proceedings of the nineteenth ACM symposium on Operating systems principles · doi:10.1145/945445.945464 · Cited by 408
Separating agreement from execution for byzantine fault tolerant services
Yin, J., Martin, J.-P., Venkataramani, A., Alvisi, L., & Dahlin, M. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945470 · Cited by 309
HQ replication: a hybrid quorum protocol for byzantine fault tolerance
Cowling, J. A., Myers, D. S., Liskov, B. H., Rodrigues, R., & Shrira, L. (2006) · doi:10.5555/1298455.1298473 · Cited by 297
An asynchronous [(n - 1)/3]-resilient consensus protocol
Bracha, G. (1984) · Proceedings of the third annual ACM symposium on Principles of distributed computing - PODC '84 · doi:10.1145/800222.806743 · Cited by 293
Martin, J.-P., & Alvisi, L. (2006) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2006.35 · Cited by 280
COCA: A secure distributed online certification authority
Zhou, L., Schneider, F. B., & Van Renesse, R. (2002) · ACM Transactions on Computer Systems · doi:10.1145/571637.571638 · Cited by 278
BAR fault tolerance for cooperative services
Aiyer, A. S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.-P., & Porth, C. (2005) · ACM SIGOPS Operating Systems Review · doi:10.1145/1095809.1095816 · Cited by 247
Attested append-only memory: making adversaries stick to their word
Chun, B.-G., Maniatis, P., Shenker, S., & Kubiatowicz, J. (2007) · Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles · doi:10.1145/1294261.1294280 · Cited by 247
Clement, A., Kapritsos, M., Lee, S., Wang, Y., Alvisi, L., Dahlin, M., & Riche, T. (2009) · Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles · doi:10.1145/1629575.1629602 · Cited by 247
Building a Secure Computer System
Gasser, M. (1988) · Medical Entomology and Zoology · Cited by 234
Martin, J.-P., & Alvisi, L. (2005) · 2005 International Conference on Dependable Systems and Networks (DSN'05) · doi:10.1109/dsn.2005.48 · Cited by 195
Reducing TCB complexity for security-sensitive applications: three case studies
Singaravelu, L., Pu, C., Härtig, H., & Helmuth, C. (2006) · Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006 · doi:10.1145/1217935.1217951 · Cited by 161
Martin, J.-P., Alvisi, L., & Dahlin, M. D. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36108-1_21 · Cited by 160
BAR fault tolerance for cooperative services
Aiyer, A. S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.-P., & Porth, C. (2005) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/1095810.1095816 · Cited by 157
How to tolerate half less one Byzantine nodes in practical distributed systems
Correia, M. P., Neves, N., & Veríssimo, P. (2004) · IEEE Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/reldis.2004.1353018 · Cited by 147
Self-citationSeparating agreement from execution for byzantine fault tolerant services
Yin, J., Martin, J.-P., Venkataramani, A., Alvisi, L., & Dahlin, M. (2003) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/945445.945470 · Cited by 142
The Rampart toolkit for building high-integrity services
Reiter, M. K. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60042-6_7 · Cited by 139
Veríssimo, P. (2006) · ACM SIGACT News · doi:10.1145/1122480.1122497 · Cited by 113
Virtual monotonic counters and count-limited objects using a TPM without a trusted OS
Sarmenta, L. F. G., van Dijk, M., O'Donnell, C. W., Rhodes, J., & Devadas, S. (2006) · Scalable Trusted Computing · doi:10.1145/1179474.1179485 · Cited by 102
Beyond one-third faulty replicas in byzantine fault tolerant systems
Li, J., & Mazières, D. (2007) · Networked Systems Design and Implementation · Cited by 101
OS diversity for intrusion tolerance: Myth or reality?
Garcia, M., Bessani, A., Gashi, I., Neves, N., & Obelheiro, R. R. (2011) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn.2011.5958251 · Cited by 101
Self-citationSingh, A. K., Das, T., Maniatis, P., Druschel, P., & Roscoe, T. (2008) · Cited by 94
Scaling Byzantine Fault-Tolerant Replication toWide Area Networks
Amir, Y., Danilov, C. B., Kirsch, J., Lane, J. W., Dolev, D., Nita-Rotaru, C., Olsen, J. I., & Zage, D. (2006) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn.2006.63 · Cited by 86
Bessani, A., Alchieri, E., Correia, M. P., & Fraga, J. S. (2008) · European Conference on Computer Systems · doi:10.1145/1352592.1352610 · Cited by 82
Self-citationThe Design of a COTS Real-Time Distributed Security Kernel
Correia, M. P., Veríssimo, P., & Neves, N. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36080-8_21 · Cited by 78
Self-citationEfficient middleware for byzantine fault tolerant database replication
Garcia, R., Rodrigues, R., & Preguiça, N. (2011) · European Conference on Computer Systems · doi:10.1145/1966445.1966456 · Cited by 61
How low can you go? recommendations for hardware-supported minimal TCB code execution
McCune, J. M., Parno, B. J., Perrig, A., Reiter, M. K., & Seshadri, A. (2008) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/1346281.1346285 · Cited by 61
Offline untrusted storage with immediate detection of forking and replay attacks
van Dijk, M., Rhodes, J., Sarmenta, L. F. G., & Devadas, S. (2007) · Scalable Trusted Computing · doi:10.1145/1314354.1314364 · Cited by 42
Cachin, C., & Samar, A. (2004) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn.2004.1311912 · Cited by 39
How Practical Are Intrusion-Tolerant Distributed Systems?
Obelheiro, R. R., Bessani, A., Lung, L. C., & Correia, M. P. (2006) · Cited by 38
Self-citationReducing TCB complexity for security-sensitive applications: three case studies
Singaravelu, L., Pu, C., Härtig, H., & Helmuth, C. (2006) · ACM SIGOPS Operating Systems Review · doi:10.1145/1218063.1217951 · Cited by 38
Classic Paxos vs. Fast Paxos: Caveat Emptor
Junqueira, F. (2007) · Cited by 19
Cited by
Towards secure and dependable software-defined networks
Kreutz, D., Ramos, F. M. V., & Verissimo, P. (2013) · Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking · doi:10.1145/2491185.2491199 · Cited by 697
Self-citationState Machine Replication for the Masses with BFT-SMART
Bessani, A., Sousa, J., & Alchieri, E. E. P. (2014) · 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks · doi:10.1109/dsn.2014.43 · Cited by 567
Self-citationSBFT: A Scalable and Decentralized Trust Infrastructure
Golan Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Seredinschi, D.-A., Tamir, O., & Tomescu, A. (2019) · 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) · doi:10.1109/dsn.2019.00063 · Cited by 362
Exploring the Attack Surface of Blockchain: A Comprehensive Survey
Saad, M., Spaulding, J., Njilla, L., Kamhoua, C., Shetty, S., Nyang, D., & Mohaisen, D. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.2975999 · Cited by 337
Wang, G., Shi, Z. J., Nixon, M., & Han, S. (2019) · Proceedings of the 1st ACM Conference on Advances in Financial Technologies · doi:10.1145/3318041.3355457 · Cited by 270
Metadata
- Authors
- Veronese, G. S., Correia, M., Bessani, A. N., Lung, L. C., & Verissimo, P.
- Venue
- IEEE Transactions on Computers
- Published
- 2013-01
- Volume
- 62
- Issue
- 1
- Pages
- 16-30
- ISSN
- 0018-9340 (ISSN-L)
- OpenAlex
- W2151426692
- Cited by
- 337
- References
- 47
- FWCI
- 12.23
- Type
- journal article
- Language
- en
- Open access
- closed
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.