Concurrency Control In A Dynamic Search Structure

Summary: Node-granular concurrency protocol for dynamic search structures with asynchronous background maintenance that physically removes deleted nodes. At-most-one locker per node, safe traversal through locked nodes, support for small multi-op transactions, bounded rotations, no deadlock. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc77ff3fc7570111d
Venue: PODS
Year: 1982
Pagerank: 0.00011050625
Overall Rank: 1,316 | 91.16%
DOI: 10.1145/588111.588156

Incoming Non-self Citations Over Time

Authors

1. Udi Manber (University of Washington)
2. Richard E. Ladner (University of Washington)

BibTeX Citation

@inproceedings{manber_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{CONCURRENCY CONTROL IN A DYNAMIC SEARCH STRUCTURE}},
        url = {https://dl.acm.org/doi/10.1145/588111.588156},
        doi = {10.1145/588111.588156},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Manber, Udi and Ladner, Richard E.},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,132	Transaction Synchronisation In Object Bases	1988	PODS	8.9925975e-05
2,575	Semantically-based Concurrency Control for Search Structures	1985	PODS	8.2761608e-05
2,862	Concurrency and Linear Hashing	1985	PODS	7.9313182e-05
5,919	Logical and Physical Versioning in Main Memory Databases	1997	VLDB	5.9478104e-05
7,164	Operation Specific Locking In B-Trees	1987	PODS	5.5954112e-05
9,007	Selective Deferred Index Maintenance & Concurrency Control in Integrated Information Systems	1985	VLDB	5.2388062e-05
13,393	Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees	1991	PODS	4.9793485e-05
13,437	Concurrent Set Manipulation Without Locking	1988	PODS	4.9793485e-05
13,465	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,164	Operation Specific Locking In B-Trees	1987	PODS
2	8,938	Concurrent Operations in Extendible Hashing	1986	VLDB
3	6,005	Concurrency Control for Adaptive Indexing	2012	VLDB
4	4,265	An Abstract Model of Database Concurrency Control Algorithms	1983	SIGMOD
5	14,327	Process Locking: A Protocol based on Ordered Shared Locks for the Execution of Transactional Processes	2001	PODS
6	2,973	The Performance of Concurrency Control Algorithms for Database Management Systems	1984	VLDB
7	13,370	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS
8	4,904	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
9	13,465	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
10	2,575	Semantically-based Concurrency Control for Search Structures	1985	PODS