Implementing fault-tolerant services using the state machine approach: a tutorial
Open accessAbstract
The state machine approach is a general method for implementing fault-tolerant services in distributed systems. This paper reviews the approach and describes protocols for two different failure models—Byzantine and fail stop. Systems reconfiguration techniques for removing faulty components and integrating repaired components are also discussed.
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
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.
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?
Attackers didn't need to compromise the tool itself, but only needed to influence authorised agents to abuse it.
“attackers didn't need to compromise the tool itself, but only needed to influence authorised agents to abuse it [99], [81], [150], [42].”
From Large language models for agentic NetOps and AIOps: Architectures, evaluation, and safety (2027) · cites this paper as [150]
Section 5, “Tolerating Faulty Clients,” and §5.2, “Defensive Programming” (page numbers unavailable), explain that a faulty client can send requests that cause a state machine to produce erroneous output, without the state machine itself being faulty. The paper does not describe attackers influencing authorised agents to abuse a tool; it discusses faulty clients making requests. (LLM, conf=0.82)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,228 · see citing works
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 · see citing works
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 · see citing works
Impossibility of distributed consensus with one faulty process
Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985) · Journal of the ACM · doi:10.1145/3149.214121 · Cited by 4,619 · see citing works
Self-stabilizing systems in spite of distributed control
Dijkstra, E. W. (1974) · Communications of the ACM · doi:10.1145/361179.361202 · Cited by 2,115 · see citing works
Notes on data base operating systems
Gray, J. (1978) · Lecture notes in computer science · doi:10.1007/3-540-08755-9_9 · Cited by 1,665 · see citing works
Reliable communication in the presence of failures
Birman, K., & Joseph, T. (1987) · ACM Transactions on Computer Systems · doi:10.1145/7351.7478 · Cited by 999 · see citing works
Schlichting, R. D., & Schneider, F. B. (1983) · ACM Transactions on Computer Systems · doi:10.1145/357369.357371 · Cited by 771 · see citing works
Self-citationThe theory and practice of reliable system design
Siewiorek, D. P., & Swarz, R. S. (1982) · Medical Entomology and Zoology · Cited by 745 · see citing works
Mullender, S. J. (1989) · Cited by 694 · see citing works
SIFT: Design and analysis of a fault-tolerant computer for aircraft control
Wensley, J. H., Lamport, L., Goldberg, J., Green, M. W., Levitt, K., Melliar-Smith, P. M., Shostak, R. E., & Weinstock, C. (1978) · Proceedings of the IEEE · doi:10.1109/proc.1978.11114 · Cited by 565 · see citing works
Using Time Instead of Timeout for Fault-Tolerant Distributed Systems.
Lamport, L. (1984) · ACM Transactions on Programming Languages and Systems · doi:10.1145/2993.2994 · Cited by 335 · see citing works
Preserving and using context information in interprocess communication
Peterson, L., Buchholz, N. C., & Schlichting, R. D. (1989) · ACM Transactions on Computer Systems · doi:10.1145/65000.65001 · Cited by 325 · see citing works
Schneider, F. B. (1984) · ACM Transactions on Computer Systems · doi:10.1145/190.357399 · Cited by 266 · see citing works
Self-citationReplication and fault-tolerance in the ISIS system
Birman, K. (1985) · ACM SIGOPS Operating Systems Review · doi:10.1145/323627.323636 · Cited by 245 · see citing works
Atomic Broadcast: From Simple Message Diffusion to Byzantine Agreement
Cristian, F., Aghili, H., Strong, R., et al. (1995) · Information and Computation · doi:10.1006/inco.1995.1060 · Cited by 244 · see citing works
The implementation of reliable distributed multiprocess systems
Lamport, L. (1978) · Computer Networks (1976) · doi:10.1016/0376-5075(78)90045-4 · Cited by 229 · see citing works
Self-Stabilization in Spite of Distributed Control
Dijkstra, E. W. (1982) · Springer eBooks · doi:10.1007/978-1-4612-5695-3_7 · Cited by 190 · see citing works
Fault-tolerant clock synchronization
Halpern, J. Y., Simons, B. B., Strong, R., et al. (1984) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/800222.806739 · Cited by 180 · see citing works
Replication and fault-tolerance in the ISIS system
Birman, K. (1985) · doi:10.1145/323647.323636 · Cited by 147 · see citing works
Synchronization in Distributed Programs
Schneider, F. B. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357162.357163 · Cited by 144 · see citing works
Self-citationByzantine clock synchronization
Lamport, L., & Melliar-Smith, P. M. (1984) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/800222.806737 · Cited by 115 · see citing works
Highly available distributed services and fault-tolerant distributed garbage collection
Liskov, B. H., & Ladin, R. (1986) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/10590.10593 · Cited by 106 · see citing works
Schneider, F. B., Gries, D., & Schlichting, R. D. (1984) · Science of Computer Programming · doi:10.1016/0167-6423(84)90009-1 · Cited by 84 · see citing works
Self-citationSIFT: design and analysis of a fault-tolerant computer for aircraft control
Wensley, J. H., Lamport, L., Goldberg, J., et al. (1979) · Microelectronics Reliability · doi:10.1016/0026-2714(79)90211-7 · Cited by 83 · see citing works
Distributed Systems: Methods and Tools for Specification. An Advanced Course
Alford, M., Ansart, J.-P., Hommel, G., et al. (1985) · Medical Entomology and Zoology · Cited by 78 · see citing works
Applications of Byzantine agreement in database systems
Molina, H. G., Pittelli, F. M., & Davidson, S. B. (1986) · ACM Transactions on Database Systems · doi:10.1145/5236.5243 · Cited by 78 · see citing works
Hutchinson, N. C., & Peterson, L. (1988) · doi:10.1145/52324.52332 · Cited by 56 · see citing works
A Paradigm for Reliable Clock Synchronization
Schneider, F. B. (1986) · Cited by 55 · see citing works
Self-citationSupplying high availability with a standard network file system
Marzullo, K., & Schmuck, F. (2003) · doi:10.1109/dcs.1988.12547 · Cited by 47 · see citing works
Reliable scheduling in a TMR database system
Pittelli, F. M., & García-Molina, H. (1989) · ACM Transactions on Computer Systems · doi:10.1145/58564.59294 · Cited by 35 · see citing works
Paradigms for distributed programs
(1985) · Lecture notes in computer science · doi:10.1007/3-540-15216-4_18 · Cited by 27 · see citing works
Early-delivery atomic broadcast
Gopal, A. S., Strong, R., Toueg, S., et al. (1990) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/93385.93430 · Cited by 26 · see citing works
Towards a theory of replicated processing
Mancini, L. V., & Pappalardo, G. C. (1988) · Lecture notes in computer science · doi:10.1007/3-540-50302-1_13 · Cited by 19 · see citing works
Implementing Fault-Tolerant Sensors*
Marzullo, K. (1989) · NASA STI Repository (National Aeronautics and Space Administration) · Cited by 17 · see citing works
Designing distributed services using refinement mappings
Aizikowitz, J. I. (1989) · eCommons (Cornell University) · Cited by 13 · see citing works
Ensuring Consistency in a Distributed Database System by Use of Distributed Semaphores
Schneider, F. B. (1979) · Cited by 12 · see citing works
Self-citationA Loosely Coupled Distributed System for Reliably Storing Data
Bernstein, A. J. (1985) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1985.232483 · Cited by 10 · see citing works
Compcon (1983) · IEEE Computer Society eBooks · Cited by 9 · 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
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
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
Analysis of identity management systems using blockchain technology
Haddouti, S. E., & Ech-Cherif El Kettani, M. D. (2019) · 2019 International Conference on Advanced Communication Technologies and Networking (CommNet) · doi:10.1109/commnet.2019.8742375 · Cited by 106 · 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
Navarro Leija, O. S., Shiptoski, K., Scott, R. G., Wang, B., Renner, N., Newton, R. R., & Devietti, J. (2020) · Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3373376.3378519 · Cited by 22 · see citing works
Self-Adapting Reliability in Distributed Software Systems
Brun, Y., Bang, J. Y., Edwards, G., & Medvidovic, N. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2412134 · Cited by 16 · see citing works
Large language models for agentic NetOps and AIOps: Architectures, evaluation, and safety
Bilal, M., Crowcroft, J., Wang, R., Xu, X., & Dustdar, S. (2027) · Computer Science Review · doi:10.1016/j.cosrev.2026.101075
“Restarts, failovers, replica changes, traffic shifts, and rollbacks can involve multiple components, and their security depends on consistency, replication, coordination, and recovery rules [131], [132].”
- Authors
- Schneider, F. B.
- Affiliations
- Cornell University (US)
- Corresponding author
- Schneider, Fred B.
- ORCID
- Schneider, Fred B.
- Venue
- ACM Computing Surveys
- Published
- 1990-12
- Volume
- 22
- Issue
- 4
- Pages
- 299-319
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2152465173
- Cited by
- 2,387
- References
- 40
- Citations by year
- 2026: 42 · 2025: 56 · 2024: 75 · 2023: 86 · 2022: 59 · 2021: 129 · 2020: 133 · 2019: 125 · 2018: 121 · 2017: 87 · 2016: 96 · 2015: 70 · 2014: 87 · 2013: 93 · 2012: 98
- FWCI
- 20.96
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Computing Surveys (publishedVersion)
- Funders
- National Science Foundation (8701103, 8320274)
- Office of Naval Research (N00014)
- 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 › Distributed and Parallel Computing Systems
- Keywords
- fault tolerance, state machine replication, distributed systems, Byzantine fault tolerance, fail-stop failures, system reconfiguration, component repair, distributed services
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
