Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods DTIC

dbj ©rice.edu In a distributed system using rollback recovery, information saved on stable storage during failure-free execution allows certain states of each process to be recovered after a failure. For example, in a deterministic system using message logging and checkpointing, a process state can be recovered only if all messages received by the process since its previous checkpoint have been logged. In a nondeterministic system using checkpointing alone, a process state can be recovered only if it has been recorded in a checkpoint. Optimistic rollback recovery methods in general record this information asynchronously, assuming that a suitable recoverable system state can be constructed for use during recovery. A system state is called recoverable if and only if it is consistent and the state of each individual process in that system state can be recovered. This paper shows that in any system using optimistic rollback recovery, there is always a unique maximum recoverable system state, extending-our previous result for systems using message logging and checkpointing. We also present a simple new algorithm for finding the maximum recoverable system state, and describe some experience with its implementation. These results can be applied both to deterministic and to nondeterministic systems. l) LD L5?PIBtMI ON STATEMENT A Approved for public releas.