Concurrency Control by Locking
Christos H. Papadimitriou · SIAM Journal on Computing · 1983
We present a geometric method for studying concurrency control by locking. When there are only two transactions, our method yields an exact characterization of safe locking policies and also of deadlock-free locking policies. Our results can be extended to more than two transactions, but in that case the problem becomes NP-complete.