Abstract/Details

CONCURRENCY CONTROL FOR DYNAMIC DATA STRUCTURES AND FAULT TOLERANCE

MANBER, UDI.  University of Washington. ProQuest Dissertations Publishing, 1982. 8226565.

Abstract (summary)

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.

Indexing (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences
Title
CONCURRENCY CONTROL FOR DYNAMIC DATA STRUCTURES AND FAULT TOLERANCE
Author
MANBER, UDI
Number of pages
117
Degree date
1982
School code
0250
Source
DAI-B 43/06, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9798661957931
University/institution
University of Washington
University location
United States -- Washington
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
8226565
ProQuest document ID
303081824
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/303081824