Coursify

Serializability of Concurrent Transactions: Locking vs Time-Stamping

Serializability of Concurrent Transactions: Locking vs Time-Stamping

Verified Sources
Sep 12, 2026

Serializability means that the effect of concurrent transaction execution is equivalent to some serial (one-at-a-time) execution order. In concurrency control, we can ensure serializability by enforcing constraints on how transactions interleave.

Two common approaches are:

  • keyword locking (e.g., Two-Phase Locking, 2PL), which prevents conflicts by restricting access to items so the schedule’s precedence graph stays acyclic.2
  • keyword time stamping / timestamp ordering, which enforces that conflicting operations follow timestamp order.

Answer to the MCQ: (iii) both (a) and (b) — both locking (2PL) and timestamp ordering can be designed to ensure serializability.3

Key terms you’ll use below: Serializability , Conflict serializability , Precedence graph , Two-phase locking , Timestamp ordering.

Footnotes

  1. 15-445/645 Database Systems (Fall 2025) - 18 Two-Phase Locking (CMU PDF) - Notes that 2PL is sufficient for conflict serializability and discusses lock manager and correctness. ↩

  2. Two-phase locking - Wikipedia - States 2PL is a pessimistic concurrency control method that guarantees conflict-serializability. ↩ ↩2

  3. Timestamp Ordering Concurrency Control (edu resource) - Explains timestamp ordering checks to ensure serializable schedules via RW/WW conflict directionality. ↩ ↩2

  4. View serializability - tutorialspoint - Discusses relationship and implementation practicality between conflict and view serializability. ↩

Two-Phase Locking (2PL) overview

1) Why conflicts matter: from interleavings to serializability

A schedule (history) of reads/writes is keyword conflict-equivalent to a serial schedule if we can reorder operations without violating conflict constraints. A classic characterization states:

  • A schedule is conflict-serializable iff the precedence graph formed by committed transactions is keyword acyclic.
  • Since conflict serializability implies view serializability, enforcing conflict serializability is a practical target.2

So concurrency control protocols often work by ensuring that cycles in the precedence graph cannot occur.

Footnotes

  1. Database transaction schedule - Wikipedia - Gives the equivalence: conflict-serializable iff precedence graph is acyclic (for committed transactions). ↩ ↩2

  2. View serializability - tutorialspoint - Discusses relationship and implementation practicality between conflict and view serializability. ↩

2) Locking: how Two-Phase Locking (2PL) ensures serializability

Core mechanism

Two-phase locking works as follows:

  • Growing phase: a transaction acquires locks as needed and does not release any.
  • Shrinking phase: once it releases its first lock, it cannot acquire any additional locks (only releases may occur).2

This discipline is precisely what prevents certain cyclic precedence-graph patterns from forming during execution.

Guarantee (serializability)

2PL is widely stated to guarantee conflict-serializability because it generates schedules whose precedence graph is acyclic when the protocol rules are followed.2 Many course notes/texts also explicitly teach that 2PL ensures serializable schedules by preventing conflicts via the lock discipline.

Important nuance:

  • Locking “prevents conflicts” (pessimistic control), but can impact performance via blocking and deadlocks; correctness is the focus here.2

Key terms in this section: Growing phase , Shrinking phase , Lock manager , Deadlock.

Footnotes

  1. 15-445/645 Database Systems (Fall 2025) - 18 Two-Phase Locking (CMU PDF) - Notes that 2PL is sufficient for conflict serializability and discusses lock manager and correctness. ↩ ↩2 ↩3

  2. Two-phase locking - Wikipedia - States 2PL is a pessimistic concurrency control method that guarantees conflict-serializability. ↩ ↩2 ↩3

  3. Lecture 8: Transactions, ACID, 2PC, 2PL, Serializability - Explains that two-phase locking ensures serializable schedules. ↩

3) Timestamping: how timestamp ordering enforces serializability

Basic idea

In timestamp ordering protocols, each transaction is assigned a timestamp. When a transaction wants to read/write a data item, the system checks whether doing so would violate the global timestamp order among conflicting operations. If it would, the transaction aborts/restarts (depending on the variant).

A key property often taught is:

  • Timestamp ordering ensures serializability because conflicting operations are forced to respect timestamp order (i.e., the induced precedence constraints align with timestamps).

Thomas write rule (variant)

A widely discussed refinement is the Thomas write rule (TWR), which reduces unnecessary aborts while preserving a correctness guarantee; instructional resources commonly describe it as maintaining serializability-like correctness via timestamp constraints.

Key terms in this section: Timestamp , Write-read (WR) conflict , Read-write (RW) conflict , Thomas write rule.

Footnotes

  1. Timestamp Ordering Concurrency Control (edu resource) - Explains timestamp ordering checks to ensure serializable schedules via RW/WW conflict directionality. ↩

  2. Thomas write rule - Learning Module - Describes Thomas Write Rule as a timestamp-ordering variant and its serializability-related correctness guarantee. ↩

How protocols enforce serializability (runtime view)

Growing phase

Locks-based

Acquire required shared/exclusive locks without releasing."

Shrinking phase

Locks-based

Release locks; no new lock acquisitions allowed."

Timestamp assignment

Timestamp-based

Each transaction gets a timestamp; system uses it for ordering checks."

Conflict check on access

Timestamp-based

If timestamp order would be violated, abort/restart (variant-dependent)."

Serializability assurance: locking vs timestamp ordering

Both can be configured to enforce serializability by preventing conflict cycles / enforcing timestamp-ordered precedence.

Pro Tip

When a question asks “serializability is ensured by …”, interpret it as: the protocol enforces a condition (acyclic precedence graph or timestamp-respecting conflicts) that implies serializability. For 2PL this is via lock discipline; for timestamp ordering this is via timestamp-based conflict rules.3

Footnotes

  1. Two-phase locking - Wikipedia - States 2PL is a pessimistic concurrency control method that guarantees conflict-serializability. ↩

  2. Timestamp Ordering Concurrency Control (edu resource) - Explains timestamp ordering checks to ensure serializable schedules via RW/WW conflict directionality. ↩

  3. Database transaction schedule - Wikipedia - Gives the equivalence: conflict-serializable iff precedence graph is acyclic (for committed transactions). ↩

Common pitfall

Not every “uses timestamps” implementation is automatically correct—serializability depends on the specific rule used for reads/writes (e.g., basic TO vs Thomas write rule). Similarly, “uses locks” only guarantees serializability if the protocol follows a serializability-preserving locking discipline like 2PL.3

Footnotes

  1. Two-phase locking - Wikipedia - States 2PL is a pessimistic concurrency control method that guarantees conflict-serializability. ↩

  2. Timestamp Ordering Concurrency Control (edu resource) - Explains timestamp ordering checks to ensure serializable schedules via RW/WW conflict directionality. ↩

  3. Thomas write rule - Learning Module - Describes Thomas Write Rule as a timestamp-ordering variant and its serializability-related correctness guarantee. ↩

MCQ: Why the correct choice is (iii) both (a) and (b)

Knowledge Check

Question 1 of 4
Q1Single choice

A schedule is conflict-serializable iff what property holds for its precedence graph (considering committed transactions)?

Explore Related Topics

1

Proving Deadlock Freedom with Four Identical Resources and Three Processes

2

Transmission Delay Independence Question (Length vs Distance vs Rate)

3

B+ Trees: Random vs Sequential Access (Which Statement Is True?)

Browse all research articles