Paper Info
Title
On the correctness of orphan management algorithms
Abstract
In a distributed system, node failures, network delays, and other unpredictable occurences 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 nonorphan, see consistent states of the shared data.
Year
DOI
Venue
1992
10.1145/146585.146616
J. ACM
Keywords
DocType
Volume
Argus distributed-computing system,serializability,orphan management algorithm,correct concurrency control algorithm,proofs show,input-output automata,orphan computation,recovery,argus,shared data,transaction management system,complete proof,high-level algorithm,consistent state,avalon,camelot,atomic actions
Journal
39
Issue
ISSN
Citations 
4
0004-5411
5
PageRank 
References 
Authors
1.34
15
4
Name
Order
Citations
PageRank
Maurice Herlihy18623920.94
Nancy A. Lynch2101701838.61
Michael J. Merritt32156412.40
William E. Weihl42614903.11