Is distributed locking harder?
PC Kanellakis, CH Papadimitriou - Proceedings of the 1st ACM SIGACT …, 1982 - dl.acm.org
Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database …, 1982•dl.acm.org
We examine the problem of determining whether a set of locked transactions, accessing a
distributed database, is guaranteed to produce only serializable schedules. For a pair of
transactions we prove that this concurrency control problem (which is polynomially solvable
for centralized databases) is in general coNP-complete. We employ a new graph-theoretic
technique and provide an efficient test for the special case of databases distributed between
two sites only.
distributed database, is guaranteed to produce only serializable schedules. For a pair of
transactions we prove that this concurrency control problem (which is polynomially solvable
for centralized databases) is in general coNP-complete. We employ a new graph-theoretic
technique and provide an efficient test for the special case of databases distributed between
two sites only.
We examine the problem of determining whether a set of locked transactions, accessing a distributed database, is guaranteed to produce only serializable schedules. For a pair of transactions we prove that this concurrency control problem (which is polynomially solvable for centralized databases) is in general coNP-complete. We employ a new graph-theoretic technique and provide an efficient test for the special case of databases distributed between two sites only.