Message logging: pessimistic, optimistic, causal, and optimal
- 1 January 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 24 (2) , 149-159
- https://doi.org/10.1109/32.666828
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 驴f驴n.Keywords
This publication has 17 references indexed in Scilit:
- Nonblocking and orphan-free message logging protocolsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Manetho: transparent roll back-recovery with low overhead, limited rollback, and fast output commitIEEE Transactions on Computers, 1992
- The causal ordering abstraction and a simple way to implement itInformation Processing Letters, 1991
- Lightweight causal and atomic group multicastACM Transactions on Computer Systems, 1991
- Recovery in distributed systems using optimistic message logging and checkpointingJournal of Algorithms, 1990
- Reliable communication in the presence of failuresACM Transactions on Computer Systems, 1987
- PublishingPublished by Association for Computing Machinery (ACM) ,1983
- A message system supporting fault tolerancePublished by Association for Computing Machinery (ACM) ,1983
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978
- The temporal logic of programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977