LCS Publication Details
Publication Title: ON THE CORRECTNESS OF ORPHAN MANAGEMENT ALGORITHMS
Publication Author: Herlihy, Maurice
Additional Authors: Lynch, Nancy, Merritt, Michael, and Weihl, William
LCS Document Number: MIT-LCS-TM-406
Publication Date: 8-1-1989
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
In a distributed system, node failures, network delays and other unpredictable occurrences can result in orphan computations - subcomputations that continue to run but whose results are no longer needed. Several algorithms have been proposed to prevent such computations from seeing inconsistent states of the shared data. In this paper, two such orphan management algorithms are analyzed. The first is an algorithm implemented in the Argus distributed computing system at MIT, and the second is an algorithm proposed at Carnegie-Mellon. The algorithms are described formally, and complete proofs of their correctness are given. The proofs show that the fundamental concepts underlying the two algorithms are very similar in that each can be regarded as an implementation of the same high-level algorithm. By exploiting properties of information flow within transaction management systems, the algorithms ensure that orphans only see states of the shared data that they could also see if they were not orphans. When the algorithms are used in combination with any correct concurrency control algorithm, they guarantee that all computations, orphan as well as non-orphan, see consistent states of the shared data.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.