A theorem in database concurrency control
Christos H. Papadimitriou · Journal of the ACM · 1982
Consider two straight-line programs A and B, and let H be a set of sequences of steps of A and B, possibly interleaved, but each containing all steps of A and B in the right order A necessary and sufficient condition ~s given for H to be realizable as the set of all sequences of steps that are legal under some insertion of lock-unlock steps between the steps of A and B.