BASE: using abstraction to improve fault tolerance
The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Abstract
Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or non-deterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, non-deterministic implementation. These examples suggest that our technique can be used in practice --- in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse.
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.
Integrity signals
Registry
Cites
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.
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
Time, clocks, and the ordering of events in a distributed system
Lamport, L. (1978) · Communications of the ACM · doi:10.1145/359545.359563 · Cited by 8,488
Practical Byzantine fault tolerance
Castro, M., & Liskov, B. H. (1999) · Operating Systems Design and Implementation · doi:10.5555/296806.296824 · Cited by 3,205
Self-citationTransaction Processing: Concepts and Techniques
Gray, J., & Reuter, A. (1992) · Cited by 3,000
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
Self-citationImplementing 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 · cited 1×
“This section provides an overview of our replication technique.”
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 · cited 1×
“This paper proposes a replication technique, BASE, that combines Byzantine fault tolerance 31 with work on data This research was partially supported by DARPA under contract F30602-98-1-0237 monitored by the Air Force Research Laboratory.”
MethodScale and performance in a distributed file system
Howard, J. H., Kazar, M. L., Menees, S. G., Nichols, D. A., Satyanarayanan, M., Sidebotham, R. N., & West, M. J. (1988) · ACM Transactions on Computer Systems · doi:10.1145/35037.35059 · Cited by 1,403 · cited 1×
“We ran a scaled-up version of the Andrew benchmark [8, 2] (which generates 1 GB of data) to compare the performance of our replicated file system and the off-the-shelf implementation of NFS in Linux 2.”
MethodRAID: high-performance, reliable secondary storage
Chen, P. M., Lee, E. K., Gibson, G. A., Katz, R. H., & Patterson, D. A. (1994) · ACM Computing Surveys · doi:10.1145/176979.176981 · Cited by 1,198
Lightweight causal and atomic group multicast
Birman, K., Schiper, A., & Stephenson, P. (1991) · ACM Transactions on Computer Systems · doi:10.1145/128738.128742 · Cited by 956
Network Time Protocol (Version 3) Specification, Implementation and Analysis
Mills, D. L. (1992) · doi:10.17487/rfc1305 · Cited by 949
Software rejuvenation: analysis, module and applications
Huang, Y., Kintala, C., Kolettis, N., & Fulton, N. D. (2002) · Twenty-Fifth International Symposium on Fault-Tolerant Computing. Digest of Papers · doi:10.1109/ftcs.1995.466961 · Cited by 926
N-VERSION PROGRAMMINC: A FAULT-TOLERANCE APPROACH TO RELlABlLlTY OF SOFTWARE OPERATlON
Chen, L., & Avizienis, A. (2005) · Twenty-Fifth International Symposium on Fault-Tolerant Computing, 1995, ' Highlights from Twenty-Five Years'. · doi:10.1109/ftcsh.1995.532621 · Cited by 398 · cited 2×
“BFTA enables an opportunistic form of N-version programming [3] — replicas can run distinct, off-the-shelf implementations of the service.”
BackgroundPractical Byzantine fault tolerance
de Castro, O. T., & Miguel, M. D. (2000) · Cited by 372
High-availability computer systems
Gray, J., & Siewiorek, D. P. (1991) · Computer · doi:10.1109/2.84898 · Cited by 339 · cited 2×
“These systems must tolerate software errors because these are a major cause of outages 13.”
BackgroundMethodWhy Aren't Operating Systems Getting Faster As Fast as Hardware?
Ousterhout, J. K. (1990) · Cited by 331
Replication in the harp file system
Liskov, B., Ghemawat, S., Gruber, R., Johnson, P., Shrira, L., & Williams, M. (1991) · Proceedings of the thirteenth ACM symposium on Operating systems principles · doi:10.1145/121132.121169 · Cited by 273 · cited 1×
“Several other systems have used wrapping techniques to replicate existing components, e.g., [10, 22, 19 , 2, 21, 24, 25].”
MethodSelf-citationHypervisor-based fault tolerance
Bressoud, T. C., & Schneider, F. B. (1995) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/224056.224058 · Cited by 250 · cited 2×
“For example, many resolve non-determinism by having a primary run the operations and ship the resulting state or a log with all non-deterministic events to the backups (e.g., [ 2 ]).”
BackgroundMethodProgram Development in Java: Abstraction, Specification, and Object-Oriented Design
Liskov, B. H., & Guttag, J. V. (1986) · International Linear Collider · Cited by 218
Self-citationProactive recovery in a Byzantine-fault-tolerant system
Castro, M., & Liskov, B. H. (2000) · doi:10.5555/1251229.1251248 · Cited by 174
Self-citationHerlihy, M. P., & Wing, J. M. (1987) · Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '87 · doi:10.1145/41625.41627 · Cited by 173
Efficient optimistic concurrency control using loosely synchronized clocks
Adya, A., Gruber, R., Liskov, B., & Maheshwari, U. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223787 · Cited by 169 · cited 1×
“Thor uses an optimistic concurrency control algorithm [1] to serialize [14] transactions.”
MethodSelf-citationAdding group communication and fault-tolerance to CORBA
Maffeis, S. (1995) · Cited by 149
Improving the scalability of fault-tolerant database clusters
Jimenez-Peris, R., Patiño-Martínez, M., Kemme, B., & Alonso, G. (2003) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/icdcs.2002.1022297 · Cited by 93
Replicated distributed programs
Cooper, E. C. (1985) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/323647.323635 · Cited by 89
Providing Persistent Objects in Distributed Systems
Liskov, B. H., Castro, M., Shrira, L., & Adya, A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48743-3_11 · Cited by 80 · cited 4×
“than t is aborted [18].”
BackgroundMethodInfluentialSelf-citationHAC: hybrid adaptive caching for distributed storage systems
Castro, M., Adya, A., Liskov, B. H., & Myers, A. C. (1997) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/268998.266666 · Cited by 61
Self-citationSupplying high availability with a standard network file system
Marzullo, K., & Schmuck, F. (2003) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/dcs.1988.12547 · Cited by 50 · cited 1×
“Several other systems have used wrapping techniques to replicate existing components, e.g., [10, 22 , 19, 2, 21, 24, 25].”
Method
Cited by
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
Self-citationZyzzyva: 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
SBFT: 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
Improving the reliability of commodity operating systems
Swift, M. M., Bershad, B. N., & Levy, H. M. (2005) · ACM Transactions on Computer Systems · doi:10.1145/1047915.1047919 · Cited by 338
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
Metadata
- Authors
- Rodrigues, R., Castro, M., & Liskov, B.
- Venue
- Proceedings of the eighteenth ACM symposium on Operating systems principles
- Publisher
- ACM
- Published
- 2001-10-21
- Pages
- 15-28
- OpenAlex
- W2053903896
- Cited by
- 166
- References
- 27
- FWCI
- 4.76
- Type
- conference paper
- 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.