On the complexity of concurrency control by locking in distributed database systems

Given a pair of locked transactions, accessing a distributed database, the problem is studied of whether this pair is safe, i.e., guaranteed to produce only serializable schedules. It is shown that an easy-to-test graph condition, which characterizes safety for a pair of locked transactions in a centralized database, also applies when the database has been distributed among at most three sites