Nested Transactions, Conflict-Based Locking, and Dynamic Atomicity.
Alan David Fekete, Nancy Ann Lynch, Michael Merritt, William E. Weihl · 1987
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.