On The Complexity Of Commit Protocols

Summary: Near-2 log n time lower bound for nonblocking commit protocols (2 log n - log log n - log log log n - O(1)), tightening prior bounds. Impossibility of simultaneously optimal time and message complexity for blocking/nonblocking commits and explicit time–message trade-offs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h460997b4730b433b
Venue: PODS
Year: 1985
Pagerank: 5.4772833e-05
Overall Rank: 7,686 | 48.33%
DOI: 10.1145/325405.325447

Incoming Non-self Citations Over Time

Authors

1. K.V.S. Ramarao (University of Pittsburgh)

BibTeX Citation

@inproceedings{ramarao_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{ON THE COMPLEXITY OF COMMIT PROTOCOLS}},
        url = {https://dl.acm.org/doi/10.1145/325405.325447},
        doi = {10.1145/325405.325447},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ramarao, K.V.S.},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,464	Transaction Commitment At Minimal Communication Cost	1987	PODS	4.9793485e-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
493	Nonblocking Commit Protocols	1981	SIGMOD	0.00017407133

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,449	Commitment In A Partitioned Distributed Database	1988	SIGMOD
2	6,693	Optimal Termination Protocols for Network Partitioning	1983	PODS
3	4,017	A Knowledge Theoretic Analysis of Atomic Commitment Protocols (Preliminary Report)	1987	PODS
4	4,427	Analysis of Distributed Commit Protocols	1982	SIGMOD
5	6,572	Performance Evaluation of a Two-Phase Commit Based Protocol for Distributed Databases	1982	PODS
6	5,412	An Optimistic Commit Protocol for Distributed Transaction Management	1991	SIGMOD
7	4,505	Revisiting Commit Processing in Distributed Database Systems	1997	SIGMOD
8	493	Nonblocking Commit Protocols	1981	SIGMOD
9	13,464	Transaction Commitment At Minimal Communication Cost	1987	PODS
10	7,739	How Fast can a Distributed Transaction Commit?	2017	PODS