Nested Transactions, Conflict-Based Locking, and Dynamic Atomicity.
Abstract
In this paper examines some concurrency control algorithms for nested transaction systems. A simple local property called dynamic atomicity is defined for data objects in such a system, and we show that all the executions of a system are serially correct (despite concurrency and transaction aborts) provided each data object is dynamic atomic. This result is applied to give a correctness proof for a new algorithm, called Conflict Based Locking, for managing data in a nested transaction system. The algorithm uses a table specifying which operations may not proceed concurrently to determine when an operation may be granted a lock on an object. The algorithm is an extension of a general conflict-based locking protocol introduced by Weihl for transaction systems without nesting. It is also similar to Moss' algorithm, which uses read- and write- locks and a stack of versions of each object to ensure the serializability and recoverability of transactions accessing the data. We show that objects implemented using Moss' algorithm of the new Conflict-Based Locking algorithm are dynamic atomic. Thus it follows that if each object in a nested transaction system uses either Moss' algorithm or the new Conflict-Based Locking algorithm, then all executions of the system will be serially correct.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1987
- Accession Number
- ADA187033
Entities
People
- Alan Fekete
- Michael Merritt
- Nancy Lynch
- William Weihl
Organizations
- Massachusetts Institute of Technology