Non-Deterministic Queue Operations

Summary: Introduces a transaction model that permits non-deterministic queue semantics to enable high-concurrency extended queue operations (non-blocking dequeue/enqueue, priority dequeue). Achieves large concurrency gains by relaxing strict ordering and using novel conflict-resolution semantics to preserve transactional correctness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 923
Venue: PODS
Year: 1991
Pagerank: 5.537774e-05
Overall Rank: 7,816 | 46.38%
DOI: 10.1145/113413.113418

Incoming Non-self Citations Over Time

Authors

1. Hector Garcia-Molina (Princeton University)
2. Kenneth Salem (University of Maryland)

BibTeX Citation

@inproceedings{garciamolina_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Non-Deterministic Queue Operations}},
        url = {https://dl.acm.org/doi/10.1145/113413.113418},
        doi = {10.1145/113413.113418},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Garcia-Molina, Hector and Salem, Kenneth},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,025	Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems	1992	PODS	5.329656e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
64	Sagas	1987	SIGMOD	0.00038756588
1,127	Implementing Recoverable Requests Using Queues	1990	SIGMOD	0.00012070177
1,276	Organizing Long-Running Activities with Triggers and Transactions	1990	SIGMOD	0.0001136991
2,793	Hybrid Concurrency Control for Abstract Data Types (Extended Abstract)	1988	PODS	8.1180419e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,430	Real-Time Transaction Scheduling: A Cost Conscious Approach	1993	SIGMOD
2	14,450	Safety Of Non-Well-Locked Transaction Systems	1986	PODS
3	13,081	An Approach to Eliminate Transaction Blocking in Locking Protocols	1992	PODS
4	1,148	Scheduling Real-time Transactions: a Performance Evaluation	1988	VLDB
5	14,533	Transactions Modeling	1982	SIGMOD
6	12,900	Concurrency Control and Recovery in Transactional Process Management	1999	PODS
7	14,538	A Formal Model for Maximum Concurrency in Transaction Systems with Predeclared Writesets	1982	VLDB
8	1,398	Queueing Network Models for Concurrent Transaction Processing in a Database System	1979	SIGMOD
9	2,089	A Transactional Model for Long-Running Activities	1991	VLDB
10	1,127	Implementing Recoverable Requests Using Queues	1990	SIGMOD