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: hf58912c0f680aa6b
Venue: PODS
Year: 1991
Pagerank: 5.4135215e-05
Overall Rank: 7,979 | 46.36%
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,194	Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems	1992	PODS	5.2100767e-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
66	Sagas	1987	SIGMOD	0.00038047495
1,149	Implementing Recoverable Requests Using Queues	1990	SIGMOD	0.00011809579
1,300	Organizing Long-Running Activities with Triggers and Transactions	1990	SIGMOD	0.00011118207
2,856	Hybrid Concurrency Control for Abstract Data Types (Extended Abstract)	1988	PODS	7.9381255e-05

Semantically Similar Papers

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