Concurrent Set Manipulation Without Locking

Summary: Lock-free concurrent set algorithm supporting insert/delete/member using only single-location atomic read-modify-write operations, no locks and no aborts. Provides order-preserving serializability via weaker conditions than prior approaches, enabling higher concurrency with simpler primitives. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 830
Venue: PODS
Year: 1988
Pagerank: 5.093636e-05
Overall Rank: 13,147 | 9.80%
DOI: 10.1145/308386.308442

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Vladimir Lanin (New York University)
2. Dennis Shasha (New York University)

BibTeX Citation

@inproceedings{lanin_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{CONCURRENT SET MANIPULATION WITHOUT LOCKING}},
        url = {https://dl.acm.org/doi/10.1145/308386.308442},
        doi = {10.1145/308386.308442},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Lanin, Vladimir and Shasha, Dennis},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
464	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00018055592
1,292	Concurrency Control In A Dynamic Search Structure	1982	PODS	0.0001130324
2,418	Concurrency Control in B+-Trees Databases Using Preparatory Operations	1985	VLDB	8.6059055e-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
3,115	Extendible Hashing for Concurrent Operations and Distributed Data	1983	PODS	7.7400134e-05
4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS	6.5091522e-05
8,776	Concurrent Operations in Extendible Hashing	1986	VLDB	5.3766157e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,751	An Almost-Serial Protocol for Transaction Execution in Main-Memory Database Systems	2002	VLDB
2	14,477	Maximal Concurrency By Locking	1984	PODS
3	4,176	An Abstract Model of Database Concurrency Control Algorithms	1983	SIGMOD
4	2,793	Hybrid Concurrency Control for Abstract Data Types (Extended Abstract)	1988	PODS
5	2,729	On-the-Fly, Incremental, Consistent Reading of Entire Databases	1985	VLDB
6	5,696	Locks with Constrained Sharing (Extended Abstract)	1990	PODS
7	4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
8	1,292	Concurrency Control In A Dynamic Search Structure	1982	PODS
9	8,776	Concurrent Operations in Extendible Hashing	1986	VLDB
10	13,080	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS