The Complexity of Reliable Concurrency Control
Christos H. Papadimitriou, Mihalis Yannakakis · SIAM Journal on Computing · 1987
We define what it means for a schedule to be reliable, that is, correct in the face of possible transaction failures (assuming that aborting a transaction to restore correctness is not allowed). It turns out that the right definition is recursive, and surprisingly involved. We show that, in fact, testing a schedule for reliability is PSPACE-complete, and thus in some sense even harder than the ordinary NP-complete notions of correctness examined in the past. However, we also prove that all conflict serializable schedules are always reliable, and thus reliability should not be an extra complication for practical concurrency control systems. Finally, we examine two other notions of reliability, related to multiple versions and aborts.