Title
Concurrent manipulation of binary search trees
Overview
To implement a concurrent binary search tree system (CBSC) that can
support any number of concurrent processes which perform searching, insertion,
deletion, and rotation on the tree, but allow any process to lock only a
constant number of nodes at any time. Also, in the systems, searches are
essentially never blocked.
Paper
H.T. Kung and Philip L. Lehman.
Concurrent manipulation of binary search trees.
ACM Transactions on Database Systems, 5(3):354-382, 1980.
Additional reading material
-
R. Bayer and M. Schkolnick.
Concurrency of operations on B-trees.
Acta Informatica, 9(1):1-21, 1977.
-
Steven Robbins.
Starving philosophers: experimentation with monitor synchronization.
In Proceedings of the 32st SIGCSE Technical Symposium on Computer
Science Education,
pages 317-321, 2001.
ACM
-
Stephen J. Hartley.
Concurrent programming: the Java programming language.
Oxford University Press. 1998.
-
Michael T. Goodrich and Roberto Tamassia.
Data structures and algorithms in Java.
Wiley.
2000.
-
Dennis Kafura.
Object-oriented software design and construction with Java.
Prentice-Hall.
2000.
Implementation details
-
CBSC system analysis and design;
-
CBSC SEARCH-INSERTION System Implementation in Java;
-
CBSC SEARCH-INSERTION-ROTATION system Implementation in Java;
-
CBSC SEARCH-INSERTION-ROTATION-DELETION system Implementation in Java;
-
CBSC simulation program using JAVA Applets.