THEORY OF SERIALIZABILITY FOR A PARALLEL MODEL OF TRANSACTIONS (Extended Abstract)

Summary: Generalizes serializability from the sequential two-step model to a parallel multi-step program-schema, defining two classes of serializable executions and extending recognition and online-scheduling results to the parallel setting. Argues online scheduling is unsuitable, introduces batch schedulers and minimal precedence constraints, and proves any optimal batch scheduler that relies only on syntactic information cannot be efficient. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 638
Venue: PODS
Year: 1982
Pagerank: 5.1972596e-05
Overall Rank: 9,912 | 32.00%
DOI: 10.1145/588111.588158

Incoming Non-self Citations Over Time

Authors

1. Ravindran Krishnamurthy (IBM; University of Texas)
2. Umeshwar Dayal (Computer Corporation of America; University of Texas)

BibTeX Citation

@inproceedings{krishnamurthy_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{THEORY OF SERIALIZABILITY FOR A PARALLEL MODEL OF TRANSACTIONS (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/588111.588158},
        doi = {10.1145/588111.588158},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Krishnamurthy, Ravindran and Dayal, Umeshwar},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,653	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.2898925e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
695	An Optimality Theory of Concurrency Control for Databases	1979	SIGMOD	0.00014910218

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,468	The Complexity of Reliable Concurrency Control	1985	PODS
2	14,538	A Formal Model for Maximum Concurrency in Transaction Systems with Predeclared Writesets	1982	VLDB
3	1,148	Scheduling Real-time Transactions: a Performance Evaluation	1988	VLDB
4	13,252	Disjoint-Interval Topological Sort: A Useful Concept in Serializability Theory (Extended Abstract)	1983	VLDB
5	13,209	A semantic approach to correctness of concurrent transaction executions	1985	PODS
6	13,021	Relative Serializability: An Approach for Relaxing the Atomicity of Transactions	1994	PODS
7	9,097	On Correctness of Non-serializable Executions	1993	PODS
8	12,877	On Herbrand Semantics and Conflict Serializability of Read-Write Transactions (Extended Abstract)	2000	PODS
9	3,384	Towards a Unified Theory of Concurrency Control and Recovery	1993	PODS
10	2,450	Formal Model of Correctness Without Serializability	1988	SIGMOD