Recovery in Distributed Systems Using Optimistic Message Logging and Checkpointing

In a distributed system using message logging and checkpointing to provide fault tolerance, there is always a unique maximum recoverable system state, regardless of the message logging protocol used. The proof of this relies on the observation that the set of system states that have occurred during any single execution of a system forms a lattice, with the sets of consistent and recoverable system states as sublat­tices. The maximum recoverable system state never decreases, and if all messages are eventually logged, the domino effect cannot occur. This paper presents a general model for reasoning about recovery in such a system and, based on this model, an efficient algo­ rithm for determining the maximum recoverable sys­tem state at any time. This work unifies existing ap­proaches to fault tolerance based on message logging and checkpointing, and improves on existing methods for optimistic recovery in distributed systems.