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: 740
Venue: PODS
Year: 1985
Pagerank: 4.8925595e-05
Overall Rank: 6,936 | 51.75%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. K.V.S. Ramarao

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,976	Transaction Commitment At Minimal Communication Cost	1987	PODS	4.1945683e-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
375	Nonblocking Commit Protocols	1981	SIGMOD	0.00025176239

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,495	Optimal Termination Protocols for Network Partitioning	1983	PODS	5.4757592e-05
12,963	Commitment In A Partitioned Distributed Database	1988	SIGMOD	4.1945683e-05
2,871	A Knowledge Theoretic Analysis of Atomic Commitment Protocols (Preliminary Report)	1987	PODS	7.97706e-05
3,567	Analysis of Distributed Commit Protocols	1982	SIGMOD	6.9622092e-05
4,585	Performance Evaluation of a Two-Phase Commit Based Protocol for Distributed Databases	1982	PODS	6.0664006e-05
5,254	An Optimistic Commit Protocol for Distributed Transaction Management	1991	SIGMOD	5.6013994e-05
4,629	Revisiting Commit Processing in Distributed Database Systems	1997	SIGMOD	6.0373208e-05
375	Nonblocking Commit Protocols	1981	SIGMOD	0.00025176239
12,976	Transaction Commitment At Minimal Communication Cost	1987	PODS	4.1945683e-05
7,666	How Fast can a Distributed Transaction Commit?	2017	PODS	4.6846408e-05