Optimal Message Logging Protocols \\ (Preliminary Version)
Lorenzo Alvisi, Keith Marzullo · eCommons (Cornell University) · 1994
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 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 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. We give several ...