Content area
Abstract
This dissertation deals with two areas in concurrency control design, concurrency control for dynamic data structures and fault tolerant concurrency control.
A design of two data structures, algorithms and a concurrency control protocol for concurrent manipulations of dynamic search structures is presented. The protocol supports the concurrent execution of generalized transactions which are sequences of basic operations which include update, insert and delete. The algorithms for these basic operations introduce only a very small overhead for the concurrency. In order to make the system even more efficient for the transactions, maintenance processes are introduced. The maintenance processes operate independently in the background to reorganize the data structure and "clean up" after the (more urgent) transactions. The interference among the transactions and the maintenance processes is minimized by a efficient locking policy which also guarantees the absence of deadlock.
A fault tolerant, deadlock free, locking protocol which overcomes failures without specifically detecting them is also presented. The main idea in the design of the protocol is to let blocked processes attempt to complete other processes work, rather than just wait for the locks to be removed. This way, a failing transaction will be completed by other processes instead of being rolled back by a central control. The protocol works only under very restrictive assumptions. Some heuristic techniques for adapting the protocol to more general applications are also examined.
