Optimal Message Logging Protocols \\ (Preliminary Version)

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.