Part 4 · 2 chapters · ~12 min

Concurrency Theory

Schedules, serial and serialisable executions, conflict serialisability and precedence graphs, view serialisability and why it is not implemented, two-phase locking (basic, strict, rigorous), deadlock prevention (wait-die, wound-wait) and detection, timestamp ordering and Thomas's write rule, optimistic concurrency control, snapshot isolation formally, write skew, serialisable snapshot isolation, and recoverable, cascadeless and strict schedules.

Serialisability, computed

code

// precedence graph from a schedule (course code)
const sched = [['T1','r','x'], ['T2','w','x'], ['T2','r','y'], ['T1','w','y']];
for (i < j) if (ti !== tj && xi === xj && (oi === 'w' || oj === 'w')) edges.add(`${ti}→${tj}`);
// real output: edges [T1→T2, T2→T1] · conflict-serialisable: false

protocol	rule	property
two-phase locking (2PL)	acquire all locks before releasing any	guarantees conflict serialisability; can deadlock
strict 2PL	hold write locks until commit	also strict schedules: no cascading aborts (what databases implement)
wait-die / wound-wait	older transactions wait or wound younger ones by timestamp	prevent deadlocks without a detector
timestamp ordering	operations must respect transaction timestamps or abort	Thomas's write rule ignores obsolete writes instead of aborting
optimistic (OCC)	run, then validate read sets at commit	cheap under low contention; aborts under high

View serialisability accepts more schedules than conflict serialisability, but testing it is NP-complete, so no system uses it. Recoverability: a schedule is recoverable if transactions commit only after those they read from; cascadeless if they read only committed data; strict if they also do not overwrite uncommitted data. Strict 2PL gives all three.

A SCHEDULE THAT IS NOT SERIALISABLE

r1(x) w2(x) r2(y) w1(y): the precedence graph has a cycle

swipe the figure sideways, or tap expand for full screen

1/4

conflicts

Two operations conflict if they come from different transactions, touch the same item, and at least one writes. Conflicts fix an order between transactions.

same item, one writeconflicts order transactions

Snapshot isolation and write skew

code

-- invariant: at least one of two joint-account approvers must stay on duty
-- both transactions start, both see two approvers on duty (their snapshots)
T1: SELECT count(*) FROM approvers WHERE on_duty;   -- 2
T2: SELECT count(*) FROM approvers WHERE on_duty;   -- 2
T1: UPDATE approvers SET on_duty = false WHERE id = 1;
T2: UPDATE approvers SET on_duty = false WHERE id = 2;   -- different row: no write-write conflict
T1: COMMIT;  T2: COMMIT;                                  -- under SI both succeed → zero on duty
-- under SERIALIZABLE (SSI) Postgres detects the read-write dependency cycle and aborts one with 40001

Formally, snapshot isolation prevents dirty reads, non-repeatable reads, phantoms (for its snapshot) and lost updates, but allows write skew: two transactions read overlapping data and write disjoint data, each preserving the invariant alone. Fekete et al. (2005) showed every SI anomaly involves two consecutive read-write ("rw-antidependency") edges in a cycle; Cahill's SSI (2008, in Postgres since 9.1) tracks those edges and aborts when the dangerous structure appears. Applications must retry on serialisation failures.