MESSAGE LOGGING - PESSIMISTIC, OPTIMISTIC, CAUSAL, AND OPTIMAL

Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All m essage-logging protocols require that, when recovery is complete, ther e be no orphan processes, which are surviving processes whose states a re inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property ''no orphan proce sses.'' From this specification, we describe how different existing cl asses of message-logging protocols (namely optimistic, pessimistic, an d a class that we call causal) implement this property. We then propos e a set of metrics to evaluate the performance of message-logging prot ocols, and characterize tile protocols that are optimal with respect t o these metrics. Finally, starting from a protocol that relies on caus al delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f: 1 l ess than or equal to f less than or equal to n.