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: 739
Venue: PODS
Year: 1985
Pagerank: 5.6029996e-05
Overall Rank: 7,540 | 48.27%
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,174	Transaction Commitment At Minimal Communication Cost	1987	PODS	5.093636e-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
480	Nonblocking Commit Protocols	1981	SIGMOD	0.00017789222

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,159	Commitment In A Partitioned Distributed Database	1988	SIGMOD
2	6,568	Optimal Termination Protocols for Network Partitioning	1983	PODS
3	3,936	A Knowledge Theoretic Analysis of Atomic Commitment Protocols (Preliminary Report)	1987	PODS
4	4,338	Analysis of Distributed Commit Protocols	1982	SIGMOD
5	6,445	Performance Evaluation of a Two-Phase Commit Based Protocol for Distributed Databases	1982	PODS
6	5,292	An Optimistic Commit Protocol for Distributed Transaction Management	1991	SIGMOD
7	4,419	Revisiting Commit Processing in Distributed Database Systems	1997	SIGMOD
8	480	Nonblocking Commit Protocols	1981	SIGMOD
9	13,174	Transaction Commitment At Minimal Communication Cost	1987	PODS
10	7,736	How Fast can a Distributed Transaction Commit?	2017	PODS