Is distributed locking harder

We examine the problem of determining whether a set of locked transactions, accessing a distributed database, is guaranteed to pro-duce 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. 1