### On the correctness of orphan management algorithmsOn the correctness of orphan management algorithms

Access Restriction
Subscribed

 Author Herlihy, Maurice ♦ Lynch, Nancy ♦ Merritt, Michael ♦ Weihl, William Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Argus ♦ Atomic actions ♦ Avalon ♦ Camelot ♦ Input-output automata ♦ Recovery ♦ Serializability Abstract In a distributed system, node failures, network delays, and other unpredictable occurences can result in $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 39 Issue Number 4 Page Count 50 Starting Page 881 Ending Page 930

#### Open content in new tab

Source: ACM Digital Library