Message logging: pessimistic, optimistic, causal, and optimal
IEEE Transactions on Software EngineeringPublished 1 January 1998
Lorenzo Alvisi, Keith Marzullo
Citations212
SJR quartileQ1
SJR score1.45
SNIP2.43
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work gives a precise specification of the consistency property "no orphan processes", and proposes a set of metrics to evaluate the performance of message-logging protocols, and describes the protocols that are optimal with respect to these metrics.
Abstract
Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All message-logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property "no orphan processes". From this specification, we describe how different existing classes of message-logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message-logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f (1/spl les/f/spl les/n).
Keywords
Computer Science
Communications of the ACMTime, clocks, and the ordering of events in a distributed system
8,437 Citations1978Leslie Lamport
A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events, and a bound is derived on how far out of synchrony the clocks can become.
The temporal logic of programs
5,586 Citations1977Amir Pnueli
A unified approach to program verification is suggested, which applies to both sequential and parallel programs, and the main proof method is that of temporal reasoning in which the time dependence of events is the basic concept.
Lecture notes in computer scienceNotes on data base operating systems
1,652 Citations1978Jim Gray
This paper is a compendium of data base management operating systems folklore and focuses on particular issues unique to the transaction management component especially locking and recovery.
ACM Transactions on Computer SystemsReliable communication in the presence of failures
996 Citations1987Ken Birman, Thomas Joseph
A review of several uses for the protocols in the ISIS system, which supports fault-tolerant resilient objects and bulletin boards, illustrates the significant simplification of higher level algorithms made possible by the approach.
ACM Transactions on Computer SystemsLightweight causal and atomic group multicast
955 Citations1991Ken Birman, André Schiper +1 more
This poster presents a probabilistic procedure to constrain the number of particles in the response of the immune system to the presence of Tau.
ACM Transactions on Computer SystemsOptimistic recovery in distributed systems
722 Citations1985Rob Strom, Shaula Yemini
Optimistic Recovery is a new technique supporting application-independent transparent recovery from processor failures in distributed systems that can tolerate the failure of an arbitrary number of processors and yields better throughput and response time than other general recovery techniques whenever failures are infrequent.
IEEE Transactions on ComputersManetho: transparent roll back-recovery with low overhead, limited rollback, and fast output commit
305 Citations1992E. N. Mootaz Elnozahy, Willy Zwaenepoel
Manetho is a new transparent rollback-recovery protocol for long-running distributed computations that achieves the advantages of pessimistic message logging and, fast output commit, and the advantage of optimistic message logging.
Sender-Based Message Logging
280 Citations1987Willy Zwaenepoel, David B. Johnson
Sender-based message logging, a low-overhead mechanism for providing transparent fault-tolerance in distributed systems, is described, which allows one to recover from a single failure at a time without the expense of synchronously logging each message to stable storage.
ACM Transactions on Computer SystemsByzantine generals in action
264 Citations1984Fred B. Schneider
Use of fail-stop processors is compared with the state machine approach, another general paradigm for constructing fault-tolerant systems.
Recovery in Distributed Systems Using Optimistic Message Logging and Checkpointing
258 Citations1988Willy Zwaenepoel, Johnson, D.B.
ACM SIGOPS Operating Systems ReviewA message system supporting fault tolerance
245 Citations1983Anita Borg, Jim Baumbach +1 more
Information Processing LettersThe causal ordering abstraction and a simple way to implement it
217 Citations1991Michel Raynal, André Schiper +1 more
A new message ordering relation, known as causal ordering, has been introduced by Birman and Joseph, and a simple algorithm to implement it is proposed, based on message sequence numbering.
Efficient distributed recovery using message logging
171 Citations1989A. Prasad Sistla, Jennifer L. Welch
Algorithm for recovery on networks, in which each process only communicates with its neighbors, and how to decompose large networks into smaller networks so that each of the smaller network can use a different recovery procedure.
A message system supporting fault tolerance
158 Citations1983Anita Borg, Jim Baumbach +1 more
A simple and general design uses message-based communication to provide software tolerance of single-point hardware failures by delivering all interprocess messages to inactive backups for both the sender and the destination.
Volatile logging in n-fault-tolerant distributed systems
114 Citations2003Rob Strom, David F. Bacon +1 more
The authors introduce two enhancements to optimistic recovery which allow messages to be logged without performing any I/O to stable storage and show that the combination of these two optimizations yields a transparent n-fault-tolerant system which logs to stablestorage only those messages received from the outside world and a very small number of additional messages.
On the use and implementation of message logging
103 Citations2002E. N. Mootaz Elnozahy, Willy Zwaenepoel
A number of experiments are presented showing that for compute-intensive applications executing in parallel on clusters of workstations, message logging has higher failure-free overhead than coordinated checkpointing, but result in much shorter output latency thancoordinated checkpointing.
Nonblocking and orphan-free message logging protocols
95 Citations2002Lorenzo Alvisi, Bruce Hoppe +1 more
Publishing
79 Citations1983Michael Powell, David L. Presotto
Simulations show that at least 5 multi-user minicomputers can be supported on a standard Ethernet using a single recorder, and demonstrates that an error recovery can be transparent to user processes and can be centralized in the network.
Crash recovery with little overhead
77 Citations2002Tony Tong-Ying Juang, S. Venkatesan
Without appending any information to the messages of the application program, it is shown that it is possible to recover from failures using O(mod V mod mod E mod ) messages where mod V mod is the number of processors and E mod isThe number of communication links in the system.
eCommons (Cornell University)Understanding the message logging paradigm for masking process crashes
43 Citations1996Lorenzo Alvisi
It is shown that causal message logging protocols combine the positive aspects of optimistic and pessimistic message logging and can be implemented in order to take advantage of the different patterns of communication that systems exhibit.
Trade-offs in implementing causal message logging protocols
32 Citations1996Lorenzo Alvisi, Keith Marzullo
This paper presents five different implementations of casual message logging, and explores how the application’s communication structure can be exploited to limit the amount of piggybacked data.
Distributed ComputingEfficient algorithms for optimistic crash recovery
30 Citations1994S. Venkatesan, Tony Tong-Ying Juang
The rollback problem as a closure problem is formulates and a centralized closure algorithm is presented together with two efficient distributed implementations for solving the problem.