The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
A survey of rollback-recovery protocols in message-passing systems
Abstract
This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols into checkpoint-based and log-based.Checkpoint-based protocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced.Log-based protocols combine checkpointing with logging of nondeterministic events, encoded in tuples called determinants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback-recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
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
Communicating Sequential Processes
Hoare, T. (1985) · Cited by 9,016
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
Transaction Processing: Concepts and Techniques
Gray, J., & Reuter, A. (1992) · Cited by 3,000
Distributed snapshots: determining global states of distributed systems
Chandy, K. M., & Lamport, L. (1985) · ACM Transactions on Computer Systems · doi:10.1145/214451.214456 · Cited by 2,443
Jefferson, D. R. (1985) · ACM Transactions on Programming Languages and Systems · doi:10.1145/3916.3988 · Cited by 2,397
Implementing remote procedure calls
Birrell, A. D., & Nelson, B. J. (1984) · ACM Transactions on Computer Systems · doi:10.1145/2080.357392 · Cited by 1,829
System structure for software fault tolerance
Randell, B. (1975) · ACM SIGPLAN Notices · doi:10.1145/390016.808467 · Cited by 1,520
Virtual Time and Global States of Distributed Systems
Mattern, F. (2002) · Cited by 1,277
Postel, J. B. (1981) · Cited by 1,130
System structure for software fault tolerance
Randell, B. (1975) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1975.6312842 · Cited by 1,095
Distributed discrete-event simulation
Misra, J. (1986) · ACM Computing Surveys · doi:10.1145/6462.6485 · Cited by 998
Checkpointing and Rollback-Recovery for Distributed Systems
Koo, R., & Toueg, S. (1987) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1987.232562 · Cited by 822
Fail-stop processors: an approach to designing fault-tolerant computing systems
Schlichting, R. D., & Schneider, F. B. (1983) · ACM Transactions on Computer Systems · doi:10.1145/357369.357371 · Cited by 769
Debugging Parallel Programs with Instant Replay
Leblanc, & Mellor-Crummey (1987) · IEEE Transactions on Computers · doi:10.1109/tc.1987.1676929 · Cited by 763
Optimistic recovery in distributed systems
Strom, R., & Yemini, S. (1985) · ACM Transactions on Computer Systems · doi:10.1145/3959.3962 · Cited by 722
Libckpt: transparent checkpointing under Unix
Plank, J. S., Beck, M. D., Kingsley, G., et al. (1995) · Cited by 576
Fault Tolerance in Distributed Systems
Jalote, P. (1994) · Medical Entomology and Zoology · Cited by 533
Detecting causal relationships in distributed computations: In search of the holy grail
Schwarz, R., & Mattern, F. (1994) · Distributed Computing · doi:10.1007/bf02277859 · Cited by 430
Proceedings of the 2000 International Conference on Parallel Processing
(2000) · Proceedings 2000 International Conference on Parallel Processing ICPP-00 · doi:10.1109/icpp.2000.876064 · Cited by 420
The performance of consistent checkpointing
Elnozahy, E. N. M., Johnson, D. B., & Zwaenepoel, W. (2003) · Proceedings/Proceedings - Symposium on Reliable Distributed Systems · doi:10.1109/reldis.1992.235144 · Cited by 356
Self-citationUsing 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
Preemptable remote execution facilities for the V-system
Theimer, M. M., Lantz, K. A., & Cheriton, D. R. (1985) · ACM SIGOPS Operating Systems Review · doi:10.1145/323627.323629 · Cited by 334
Preserving and using context information in interprocess communication
Peterson, L. L., Buchholz, N. C., & Schlichting, R. D. (1989) · ACM Transactions on Computer Systems · doi:10.1145/65000.65001 · Cited by 325
Manetho: transparent roll back-recovery with low overhead, limited rollback, and fast output commit
Elnozahy, E. N. M., & Willy Zwaenepoel, Y. (1992) · IEEE Transactions on Computers · doi:10.1109/12.142678 · Cited by 305
Self-citationRecovery in Distributed Systems Using Optimistic Message Logging and Checkpointing
Willy Zwaenepoel, Y., & Johnson, D. B. (1988) · Cited by 262
Self-citationConsistent global states of distributed systems: fundamental concepts and mechanisms
Babaoğlu, Ö., & Marzullo, K. (1993) · Cited by 250
Hypervisor-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
Necessary and sufficient conditions for consistent global snapshots
Netzer, R. H. B., & Xu, J. (1995) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.342127 · Cited by 238
Message logging: pessimistic, optimistic, causal, and optimal
Alvisi, L., & Marzullo, K. (1998) · IEEE Transactions on Software Engineering · doi:10.1109/32.666828 · Cited by 215
Self-citationLow-cost checkpointing and failure recovery in mobile computing systems
Prakash, R., & Singhal, M. (1996) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.539735 · Cited by 185
Designing a process migration facility: the Charlotte experience
Artsy, Y., & Finkel, R. (1989) · Computer · doi:10.1109/2.35213 · Cited by 184
An efficient implementation of vector clocks
Singhal, M., & Kshemkalyani, A. D. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90028-t · Cited by 175
Efficient distributed recovery using message logging
Sistla, A. P., & Welch, J. L. (1989) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/72981.72997 · Cited by 172
The Evolution of the Recovery Block Concept
Randell, B., & Xu, J. (1994) · doi:10.25405/ncl.34123503 · Cited by 172
Checkpointing distributed applications on mobile computers
Acharya, A., & Badrinath, B. R. (2002) · International Conference on Parallel and Distributed Information Systems · doi:10.1109/pdis.1994.331730 · Cited by 164
State Restoration in Systems of Communicating Processes
Russell, D. L. (1980) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1980.230469 · Cited by 154
An analysis of communication induced checkpointing
Alvisi, L., Elnozahy, E. N. M., Rao, S., Husain, S. A., & de Mel, A. (2003) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1999.781058 · Cited by 136
Self-citationQuasi-synchronous checkpointing: Models, characterization, and classification
Manivannan, D., & Singhal, M. (1999) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.780865 · Cited by 129
Optimal tracing and replay for debugging message-passing parallel programs
Netzer, R. H. B., & Miller, B. P. (1992) · Conference on High Performance Computing (Supercomputing) · doi:10.5555/147877.148058 · Cited by 119
Recovery in distributed systems using optimistic message logging and checkpointing
Johnson, D. B., & Willy Zwaenepoel, Y. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90022-7 · Cited by 117
Self-citationCausal distributed breakpoints
Fowler, J., & Willy Zwaenepoel, Y. (2002) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/icdcs.1990.89277 · Cited by 115
Nonblocking and orphan-free message logging protocols
Alvisi, L., Hoppe, B., & Marzullo, K. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1993.627318 · Cited by 97
Self-citationThe Delta-4 extra performance architecture (XPA)
Barrett, P., Hilborne, A. M., Bond, P. G., Seaton, D., Veríssimo, P., Rodrigues, L., & Speirs, N. A. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1990.89386 · Cited by 93
Fail-Safe PVM: A Portable Package for Distributed Programming with Transparent Recovery
Leon, J., Fisher, A. L., & Steenkiste, P. (1993) · Defense Technical Information Center (DTIC) · doi:10.21236/ada266594 · Cited by 92
A communication-induced checkpointing protocol that ensures rollback-dependency trackability
Baldoni, R., Hélary, J.-M., Mostéfaoui, A., & Raynal, M. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1997.614079 · Cited by 92
Message logging: pessimistic, optimistic, and causal
Alvisi, L., & Marzullo, K. (2002) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.1995.500024 · Cited by 91
Self-citationMemory exclusion: optimizing the performance of checkpointing systems
Plank, J. S., Chen, Y., Li, K., Beck, M. D., & Kingsley, G. (1999) · Software Practice and Experience · Cited by 89
A software instruction counter
Mellor‐Crummey, J., & LeBlanc, T. J. (1989) · ACM SIGARCH Computer Architecture News · doi:10.1145/68182.68189 · Cited by 87
Optimistic message logging for independent checkpointing in message-passing systems
Wang, Y., & Fuchs, W. K. (2003) · IEEE Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/reldis.1992.235132 · Cited by 76
Self-citationEgida: an extensible toolkit for low-overhead fault-tolerance
Rao, S., Alvisi, L., & Vin, H. M. (2003) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1999.781033 · Cited by 73
Self-citationConcurrent robust checkpointing and recovery in distributed systems
Leu, P.-J., & Bhargava, B. (2003) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1988.105457 · Cited by 73
How to recover efficiently and asynchronously when optimism fails
Damani, O. P., & Garg, V. K. (2002) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.1996.507907 · Cited by 72
Optimal tracing and incremental reexecution for debugging long-running programs
Netzer, R. H. B., & Weaver, M. H. (1994) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/178243.178477 · Cited by 68
Finding consistent global checkpoints in a distributed computation
Manivannan, D., Netzer, R. H. B., & Singhal, M. (1997) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.595580 · Cited by 64
Checkpoint space reclamation for uncoordinated checkpointing in message-passing systems
Wang, Y., Chung, P.-Y., Lin, I.-J., & Fuchs, W. K. (1995) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.382324 · Cited by 61
Self-citationPreventing useless checkpoints in distributed computations
Hélary, J.-M., Mostéfaoui, A., Netzer, R. H. B., & Raynal, M. (2002) · IEEE Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/reldis.1997.632814 · Cited by 57
A recoverable distributed shared memory integrating coherence and recoverability
Kermarrec, A.-M., Cabillic, G., Gefflaut, A., Morin, C. A., & Puaut, I. (2002) · doi:10.1109/ftcs.1995.466970 · Cited by 57
Tsai, J., Kuo, S., & Wang, Y. (1998) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.730526 · Cited by 52
Self-citationKim, K. H. (1988) · IEEE Transactions on Software Engineering · doi:10.1109/32.6160 · Cited by 37
Roll-forward and rollback recovery: performance-reliability trade-off
Pradhan, D. K., & Vaidya, N. H. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1994.315642 · Cited by 30
Fault tolerant programming for network based parallel computing
Clematis, A. (1994) · Microprocessing and Microprogramming · doi:10.1016/0165-6074(94)90036-1 · Cited by 4
Cited by
A Survey on Distributed Machine Learning
Verbraeken, J., Wolting, M., Katzy, J., Kloppenburg, J., Verbelen, T., & Rellermeyer, J. S. (2021) · ACM Computing Surveys · doi:10.1145/3377454 · Cited by 872
Vigilante: end-to-end containment of internet worms
Costa, M., Crowcroft, J., Castro, M., Rowstron, A., Zhou, L., Zhang, L., & Barham, P. (2005) · ACM SIGOPS Operating Systems Review · doi:10.1145/1095809.1095824 · Cited by 441
The Stratosphere platform for big data analytics
Alexandrov, A., Bergmann, R., Ewen, S., Freytag, J.-C., Hueske, F., Heise, A., Kao, O., Leich, M., Leser, U., Markl, V., et al. (2014) · The VLDB Journal · doi:10.1007/s00778-014-0357-y · Cited by 432
Addressing failures in exascale computing
Snir, M., Wisniewski, R. W., Abraham, J. A., Adve, S. V., Bagchi, S., Balaji, P., Belak, J., Bose, P., Cappello, F., Carlson, B., et al. (2014) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342014522573 · Cited by 373
Architecture Design for Soft Errors
(2008) · Elsevier eBooks · doi:10.1016/b978-0-12-369529-1.x5001-0 · Cited by 365
Metadata
- Authors
- Elnozahy, E. N. (., Alvisi, L., Wang, Y.-M., & Johnson, D. B.
- Venue
- ACM Computing Surveys
- Published
- 2002-09
- Volume
- 34
- Issue
- 3
- Pages
- 375-408
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2100970777
- Cited by
- 1,804
- References
- 61
- FWCI
- 130.55
- 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.