JavaScript is disabled for your browser. Some features of this site may not work without it.
Optimal Message Logging Protocols \\ (Preliminary Version)

Author
Alvisi, Lorenzo; Marzullo, Keith
Abstract
Message logging protocols are an integral part of a technique for implementing processes that can recover from crash failures. All message logging protocols require that the state of a recovered process be consistent with the states of the other processes. This consistency requirement is usually expressed in terms of {\em orphan processes\/}, surviving processes whose states are inconsistent with the recovered state of a crashed process. Orphans are either avoided through careful logging or are eliminated through a somewhat complex recovery protocol. We give a specification of the consistency property "no orphan processes". From this specification, we describe how different existing classes of message logging protocols (namely {\em optimistic}, {\em pessimistic}, and a class that we call {\em 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 {\em optimal} with respect to these metrics. We give several examples of optimal message logging protocols that can tolerate $f$ overlapping failures and recoveries for a parameter $f: 1 \le f \le n$, and discuss the tradeoffs that arise in the implementation of these protocols.
Date Issued
1994-10Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1457
Type
technical report