On the Correctness of Orphan Management Algorithms
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 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 are 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1989
- Accession Number
- ADA213777
Entities
People
- Maurice Herlihy
- Michael Merritt
- Nancy Lynch
- William Weihl
Organizations
- Massachusetts Institute of Technology