Concurrency control in a dynamic search structure

Publisher Website
Google Scholar
Abstract
A design of a data structure and efficient algorithms for concurrent manipulations of a dynamic search structure by independent user processes is presented in this paper. The algorithms include updating data, inserting new elements, and deleting elements. The algorithms support a high level of concurrency. Each of the operations listed above requires only constant amount of locking. In order to make the system even more efficient for the user processes, maintenance processes are introduced. The maintenance processes operate independently in the background to reorganize the data structure and “clean up” after the (more urgent) user processes. A proof of correctness of the algorithms is given and some experimental results and extensions are examined.

This publication has 8 references indexed in Scilit: