The pitfall paradox and its solution with virtual objects (Q1116324)

The M-pitfall protocol is a general non-two-phase locking protocol for databases organized as directed acyclic graphs which supports shared (S-) and exclusive (X-)locks. It has the paradoxical property that in many simple situations concurrency is reduced if S-locks are used instead of X-locks. We present a technique which uses additional virtual objects and which removes this deficiency and which, under certain conditions, allows higher concurrency than the M-pitfall protocol even if only X-locks are used.