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: 636
Venue: PODS
Year: 1982
Pagerank: 0.0001130324
Overall Rank: 1,292 | 91.14%
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,084	Transaction Synchronisation In Object Bases	1988	PODS	9.1973681e-05
2,526	Semantically-based Concurrency Control for Search Structures	1985	PODS	8.463742e-05
2,801	Concurrency and Linear Hashing	1985	PODS	8.1117099e-05
5,809	Logical and Physical Versioning in Main Memory Databases	1997	VLDB	6.0801663e-05
7,026	Operation Specific Locking In B-Trees	1987	PODS	5.7232444e-05
8,845	Selective Deferred Index Maintenance & Concurrency Control in Integrated Information Systems	1985	VLDB	5.3584969e-05
13,103	Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees	1991	PODS	5.093636e-05
13,147	Concurrent Set Manipulation Without Locking	1988	PODS	5.093636e-05
13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS	5.093636e-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,026	Operation Specific Locking In B-Trees	1987	PODS
2	8,776	Concurrent Operations in Extendible Hashing	1986	VLDB
3	5,903	Concurrency Control for Adaptive Indexing	2012	VLDB
4	4,176	An Abstract Model of Database Concurrency Control Algorithms	1983	SIGMOD
5	14,016	Process Locking: A Protocol based on Ordered Shared Locks for the Execution of Transactional Processes	2001	PODS
6	2,911	The Performance of Concurrency Control Algorithms for Database Management Systems	1984	VLDB
7	13,080	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS
8	4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
9	13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
10	2,526	Semantically-based Concurrency Control for Search Structures	1985	PODS