article · 1990
A Simple Algorithm for Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods
David B. Johnson, Peter J. Keleher, Willy Zwaenepoel
Cited by 0Abstract and details only
Abstract
In a distributed system using rollback recovery, information saved on stable storage during failure-free execution allows certain states of each process to be restored after a failure. For example, in a system of deterministic processes using message logging and checkpointing, a process state can be restored only if all messages received by the process since its previous checkpoint have been logged. In a system of nondeterministic processes using checkpointing alone, a process state can be restored 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 component process can be restored. This paper presents a simple algorithm for nding the maximum recoverable system state at any time in a system using optimistic rollback recovery. We show that in such a system, there is always a unique maximum recoverable system state, extending our previous result for deterministic systems using message logging and checkpointing. These new results can be applied both to deterministic and to nondeterministic systems. We have implemented this algorithm on a collection of SUN workstations running the V-System. The algorithm requires no additional communication in the system, and requires little storage for execution. 1
Cite this paper
Johnson, D. B., Keleher, P. J., & Zwaenepoel, W. (1990). A Simple Algorithm for Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods.
Johnson, David B., et al. “A Simple Algorithm for Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods.” 1990.
Johnson, David B., Peter J. Keleher, and Willy Zwaenepoel. 1990. “A Simple Algorithm for Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods.”
Johnson, D.B., Keleher, P.J. and Zwaenepoel, W. (1990) ‘A Simple Algorithm for Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods’.
@article{johnson1990simple,
title = {{A Simple Algorithm for Finding the Maximum Recoverable System State in Optimistic Rollback Recovery Methods}},
author = {Johnson, David B. and Keleher, Peter J. and Zwaenepoel, Willy},
year = {1990}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.