Two-Phase Locking and Timestamp Ordering for GATE: Recoverable and Cascadeless Schedules Solved

Concurrency-control questions stack two decisions together. Does the protocol force a serializable order, and can the resulting schedule recover cleanly after a failure? Students often answer the first and assume the second, but protocol guarantees and recovery classes are separate properties that can both be checked on the same schedule.

Two-Phase Locking in one screen

Two-Phase Locking, or 2PL, divides every transaction into two phases:

1. In the growing phase, it may acquire locks but may not release any.

2. In the shrinking phase, it may release locks but may not acquire another lock.

The first unlock ends growth. If a transaction unlocks one item and later requests a new lock, it violates 2PL.

Basic 2PL generates conflict-serializable schedules. Each transaction has a lock point, the instant at which it obtains its final lock, and the order of lock points gives the equivalent serial order. This guarantee does not by itself promise deadlock freedom or clean recovery.

The variants change what is held and for how long:

• Strict 2PL holds every exclusive lock until commit or abort.

• Rigorous 2PL holds both shared and exclusive locks until commit or abort.

• Conservative 2PL obtains every required lock before the transaction starts. It is deadlock-free because a running transaction never waits for an additional lock, although advance knowledge reduces flexibility.

Timestamp Ordering in one screen

Timestamp Ordering, or TO, gives each transaction Ti a timestamp TS(Ti) when it starts. Every item X stores:

• R-TS(X), the largest timestamp of a transaction that has successfully read X.

• W-TS(X), the timestamp of the transaction whose write currently determines X.

For Ri(X), abort Ti if TS(Ti) < W-TS(X). Otherwise allow the read and set R-TS(X) = max(R-TS(X), TS(Ti)).

For Wi(X), basic TO aborts Ti if TS(Ti) < R-TS(X) or TS(Ti) < W-TS(X). Otherwise it accepts the write and sets W-TS(X) = TS(Ti).

Thomas' Write Rule changes the second stale-write case. If TS(Ti) < W-TS(X), the write is obsolete, so the protocol ignores it instead of aborting the transaction. The earlier test against R-TS(X) still matters.

Basic TO is conflict-serializable and deadlock-free because it aborts instead of waiting. It is not necessarily recoverable unless a stricter variant prevents unsafe access to uncommitted values.

The recovery classes, nested

The classes answer increasingly strong questions about reads, writes and commits:

• Recoverable: if Tj reads a value written by Ti, then Tj commits only after Ti commits.

• Cascadeless, or ACA: a transaction reads an item only after the transaction that wrote that version has committed. Dirty reads cannot occur.

• Strict: after Ti writes X, no other transaction may read or write X until Ti commits or aborts. Dirty reads and dirty writes are blocked.

• Serial: one transaction completes before the next transaction's operations begin.

The containment order is Serial inside Strict, inside Cascadeless, inside Recoverable, inside all schedules. A strict schedule is therefore cascadeless and recoverable, but a recoverable schedule need not be cascadeless.

Fully worked schedule classification

Classify:

S = W1(X); R2(X); W2(X); C1; C2

Read it from left to right.

1. W1(X) makes the value of X written by T1 the current version.

2. R2(X) reads that value before C1, so T2 performs a dirty read from T1.

3. W2(X) also occurs before T1 commits, so the schedule permits a dirty write on X.

4. C1 comes before C2. The reader T2 therefore commits after the writer from which it read.

The schedule is recoverable because the read-from dependency is T1 -> T2 and the commit order is also C1 -> C2. It is not cascadeless because R2(X) occurs before C1. It is also not strict because T2 both reads and writes X before T1 finishes.

Verdict: recoverable but not cascadeless.

Now swap only the commits:

S' = W1(X); R2(X); W2(X); C2; C1

The read-from dependency remains T1 -> T2, but the commit order is now C2 -> C1. T2 commits using dirty data while T1 is still uncommitted. If T1 later aborts, the committed T2 cannot be rolled back as part of ordinary cascading recovery. Therefore S' is not recoverable.

Worked Timestamp-Ordering trace with Thomas' Write Rule

Let R-TS(X) = 0 and W-TS(X) = 0. Let TS(T1) = 5 and TS(T2) = 10.

Check the Thomas case in the correct order. At W1(X), the first stale-write test is TS(T1) < R-TS(X), which becomes 5 < 5 and is false. The second test is TS(T1) < W-TS(X), which becomes 5 < 10 and is true. That is precisely the case Thomas changes from abort to ignore.

The operation stream has not changed. Only the named protocol variant has changed, so a GATE answer must state whether the question uses basic TO or Thomas' Write Rule.

Tie the protocol back to the schedule

Return to S. After W1(X), Strict 2PL makes T1 hold its exclusive lock on X until C1 or an abort. R2(X) needs a shared lock and W2(X) needs an exclusive lock, so both must wait. The dirty read and dirty write that made S non-cascadeless cannot appear in that position.

This shows why Strict 2PL gives strict schedules. Holding the last writer's exclusive lock blocks other reads and writes until the writer finishes, which also guarantees cascadelessness and recoverability. Basic 2PL can release an exclusive lock during its shrinking phase before commit, so it does not automatically provide those recovery properties.

The traps GATE plants

• "2PL prevents deadlock." False. Basic, strict and rigorous 2PL can deadlock. Conservative 2PL is the deadlock-free variant.

• "Every conflict-serializable schedule can be generated by 2PL." False. Every 2PL schedule is conflict-serializable, but some conflict-serializable schedules cannot be generated under 2PL.

• "Recoverable is the strongest recovery class." False. In the usual containment chain, strict is stronger than cascadeless, which is stronger than recoverable.

• "Basic TO is recoverable because it is serializable." False. Serializability and recoverability are different properties.

• "Thomas' Write Rule changes every TO rejection into ignore." False. It ignores the obsolete-write case against W-TS; a violation against R-TS still causes an abort.

Questions can ask for a schedule class, whether 2PL can generate an order, whether deadlock is possible, or how many TO operations are accepted, ignored or aborted. Check the current DBMS scope in the brochure on the official GATE 2026 portal of the organising IIT.

The short version and next step

Keep three lines ready: 2PL implies conflict serializability; Strict 2PL also forces strict, cascadeless and recoverable schedules; and the recovery classes nest as Serial < Strict < Cascadeless < Recoverable.

Use Transactions and concurrency control in DBMS for ACID and precedence-graph serializability; use the worked schedule and Timestamp-Ordering trace here for recovery classes and Thomas' Write Rule. Test those distinctions with DBMS Transaction MCQs. Build the wider theory in GATE Guidance by Sanchit Sir and practise schedule sets in the GATE Test Series. Choose the next subject guide from the GATE category.