Optimal Message Logging Protocols \\ (Preliminary Version)
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
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