Is distributed locking harder? (Q1061510)

The problem of determining whether a set of locked transactions, accessing a distributed database, is guaranteed to produce only serializable schedules is examined. For a pair of transactions, with n steps, it is proved that this concurrency control problem, which is polynomially solvable for centralized databases, is in general coNP- complete. A new graph-theoretic technique is employed and an \(O(n^ 2)\) test for the special case of databases distributed between two sites is provided.