—

Database Design and Applications

Concurrency Control: Lock-Based and Timestamp-Based Protocols

Published: 2026-08-06

Level: postgraduate

Audience: Postgraduate students in Database Design and Applications

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Transactions and the ACID properties — covered in Lectures 1 and 15
Schedules, conflict serializability, and the precedence graph — covered in Lectures 12 and 15
Recoverability and cascading rollback — covered in Lecture 15
Shared and exclusive locks, two-phase locking, and timestamp ordering — covered in Lecture 15

Concurrency Control: Lock-Based and Timestamp-Based Protocols

16.1 Why Concurrency Control at All

16.1.1 The Scope of This Session

Hook: A database that allows only one user at a time would be correct — and useless. Ask yourself: what does a database engine actually do when thousands of people hit the same server at the same instant? This session answers that question from the inside.

This session covers transaction control from the implementation side: how a database engine actually uses a timestamp-based protocol and a lock-based protocol to keep concurrent transactions safe, and (mentioned as part of the agenda) how a database recovers after failures. The learning model to adopt: the recorded sessions carry the primary knowledge, and this live session is meant to give a complementary, integrated understanding — the same content viewed from a different angle, so it sticks.

There is also a promise about the indexing chapter: almost every indexing technique studied there is available directly in SQL. A database user can create indexes, choose where to store them, and decide between B+ tree and other index structures; the course material is the knowledge that lets a practitioner tell the database which type of indexing the workload needs. A lab sheet demonstrating these SQL indexing facilities may be shared.

16.1.2 The Motivation: Everyone Booking at Once

Before touching any protocol, the fundamental question: why do we need concurrency at all? Consider the everyday scenario — booking a railway reservation, a flight, a hotel, buying something on an e-commerce site, paying with a digital wallet, or accessing any online service from a phone app or a desktop browser. Every one of those requests reaches a particular server, and all of them arrive concurrently. If simultaneous access were simply forbidden, the rule would be: only one user gets the database at a time. One person books; everyone else — the other six people trying to book flights — is told to wait. Until the first user finishes paying, nobody else touches anything.

That serial approach guarantees correctness, but it costs two things that matter to any real system:

User experience and response time. Users will drop off. The response time is defined as the time from when you request something until the first reply from the processor — the first response that tells you the system heard you. Even if the total work eventually takes the same amount of time (the same processor does the same total work regardless of ordering, just with more context switches), the user waiting at a screen perceives a delay and leaves. The flight website that makes you wait in line loses the sale.
Processor utilization. There is a huge read–write delay (input–output delay) inside a real transaction. A user first queries the database — how many seats are available, at what price — then decides, then types in the seat, the meal preference, the payment details. That typing is pure idle time for the processor. Without concurrency, the processor stands idle while one user types. With concurrency, the moment one transaction finishes its current instruction, the processor context-switches to another transaction and serves its query; when that one needs user input, the processor switches again. The processor never waits for input; it is always executing something.

Intuition — the context-switch story (the professor's own). Imagine a single ticket clerk and a long queue of customers. If the clerk serves one customer completely — wait for them to search their bag, fumble for cash, decide on the meal — everyone else stands idle, and the queue moves at the speed of the slowest customer. The clerk's time is wasted waiting for humans. Now make the clerk switch: serve customer 1's question, then while customer 1 types their details, serve customer 2's question, and so on. The clerk is busy the entire shift; nobody perceives a long silent wait. That is exactly what a processor does when it context-switches between transactions. The analogy breaks in one place: a clerk can still only answer one question at a time, so the total work time is unchanged — concurrency buys responsiveness and utilization, not extra capacity.

A useful way to see the two benefits together is a timeline. Draw one axis as time and the other as processor busy / idle:

Serial execution: long idle gaps (one per user typing session) punctuated by bursts of processing. The processor utilization curve looks like a spiky, mostly empty line.
Interleaved execution: the same total bursts, but packed together with no idle gaps — the utilization curve is a dense, near-solid band.

The one-sentence takeaway: concurrency reshapes when work happens (filling idle gaps), not how much work happens.

These two benefits — better response time for users and maximum processor utilization — are why concurrent access is not optional but mandatory. So the database faces a simultaneous demand: many transactions want to run at once (the application requires it, the processor wants it), and yet every one of them must still satisfy the guarantees transactions are built on.

16.1.3 The Contract That Must Hold: Transactions and ACID

A transaction is a set of instructions that must be executed either all at once or not at all — an indivisible unit. Before and after a transaction runs, the database's constraints must hold (consistency), concurrent transactions must not see each other's half-done work (isolation), and once a transaction commits, its effects must be permanent (durability). Together with atomicity these are the ACID properties.

Property	What it guarantees	The failure it prevents
Atomicity	All instructions run, or none do — no partial transaction	Money debited but no ticket issued
Consistency	Constraints hold before and after the transaction	Accounts that don't add up to the total
Isolation	No transaction sees another's uncommitted, half-done work	A reader basing a decision on a value that later disappears
Durability	Committed effects survive crashes	A confirmed booking vanishing after a power cut

Worked example — the flight booking as one transaction. A passenger books a flight through a portal. Inside the engine, this is a single transaction containing three writes:

Debit the passenger's account: balance falls from 50,000 to 45,800 (fare 4,000 + taxes 200).
Issue the ticket in the passenger's name: a new ticket row with PNR, flight number, seat.
Mark the seat booked: the seat's status changes from available to held.

Now suppose a crash happens after step 1 but before step 3. With atomicity, the engine treats the whole thing as one unit: none of the steps count. The account is restored to 50,000, no ticket exists, the seat stays available — the passenger can try again. Without atomicity, the passenger would be left with a debited account and no ticket, and the airline would show a seat as both sold and available.

Final answer: atomicity means the three writes behave as one indivisible instruction — debit and ticket and seat, or none of them. Sense-check: one unit in, one unit out — no partial outcomes, no way for a crash to split the transaction into fragments.

The flight booking shows why this matters: one person's booking is treated as a single transaction. Either the whole thing happens — money debited from the account, ticket issued in the passenger's name, seat marked booked — or none of it happens: no debit, no reservation, no seat. A crash in the middle must not leave a passenger with a debited account and no ticket. If concurrent execution breaks any of these guarantees, the application becomes inconsistent and the database loses persistence — "chaos," as the material frames it. This is fundamental, not optional.

Scope: ACID is the contract, not the mechanism. Atomicity is implemented by recovery machinery (logs and rollback), isolation is implemented by the concurrency-control protocols of this session, and durability is implemented by write-back to secondary storage. When you read "the protocol guarantees ACID," the precise claim is: the protocol prevents concurrent execution from violating these properties — the properties themselves are enforced by other components. Locking and timestamps order access; they do not, by themselves, roll back a transaction or flush a buffer.

16.1.4 From Theory to Implementation: Serializability Recap

Previous sessions established the theoretical side: given a fixed set of transactions, can we decide whether a schedule is safe? A schedule is a statement of the order in which the instructions of multiple transactions executed. A conflict serializable schedule is one whose order is equivalent to some serial schedule — the same result as if the transactions had run one after another. There was also view serializability, a weaker notion. Those are the theoretical screening tools for a schedule presented all at once: given a complete schedule, should we allow it or not?

The problem this session solves is different: transactions do not arrive as a complete schedule — they arrive on the fly. Each new transaction enters the system while others are mid-execution, and the engine must decide in real time, instruction by instruction, whether to let it proceed. The answer must come at the local, implementation level, and there are two classic mechanisms: the lock-based protocol and the timestamp-based protocol. Both have the same agenda: make sure that only conflict serializable schedules get executed, so the ACID properties survive even though many transactions interleave.

Recap + bridge. Concurrency is not a luxury — it is the response-time and processor-utilization engine behind every booking, payment, and e-commerce site, and it must be safe as well as fast. The contract it must not break is ACID; the theoretical yardstick is serializability. The two mechanisms that enforce the yardstick at implementation level are the lock-based protocol and the timestamp-based protocol, and both are examined in detail in the sections that follow. Alongside them sits a third actor in this story: the recovery subsystem, which handles what happens when the system crashes mid-transaction.

Where this matters in the field: every railway reservation portal (IRCTC), every flight and hotel booking system, every e-commerce checkout and UPI digital-wallet payment runs on exactly this combination — concurrent transactions protected by lock-based or timestamp-based protocols, backed by recovery. The design decisions in this chapter are the ones those production engines are built from, not classroom abstractions.

16.2 Lock-Based Protocols

16.2.1 Shared Locks and Exclusive Locks

A lock is a permission gate attached to a data item. When a transaction wants to touch a data item $Q$ , it first acquires a lock on $Q$ , and while the lock is held, other transactions are constrained. There are two kinds:

Exclusive lock (write lock): the holder is the only one allowed to access the item — nobody else can read it or write it.
Shared lock (read lock): the holder can read the item, and other transactions may also acquire a shared lock and read it, but no one may write it while any shared lock is held.

The compatibility rule (the whole of shared/exclusive locking in one table). A new lock request is granted only if it does not conflict with a lock already held:

	Shared lock held	Exclusive lock held
Request shared	✅ granted (both read together)	❌ denied — wait
Request exclusive	❌ denied — wait	❌ denied — wait

A data item with a shared lock on it is read-locked: many readers can share it, but no writer may enter. A data item with an exclusive lock is write-locked: exactly one transaction, and nobody else — not even a reader. This is the same compatibility matrix used by every real lock manager, from textbooks to MySQL InnoDB.

The protocol pattern is acquire → use → release, repeated: a transaction locks the item it needs, works on it, unlocks it, moves to the next item, locks it, works, unlocks — over and over. This is the decision point at the logical level: when a transaction requests a lock and the item is already locked incompatibly, the request is denied and the transaction waits; when the holder releases, the waiter gets in. This provides a time ordering: if the item is locked for writing, a reader that comes later simply cannot see it until the write completes and the lock is released. Its access happens at the later time, when the lock is granted.

The machinery behind the scenes: a lock manager keeps a lock table recording, for each locked item, the lock mode and the holding transactions. For a read-locked item the table counts the number of concurrent readers (the lock is released only when the count drops to zero); for a write-locked item it records the single holder. Requests that cannot be granted are queued and awakened when the item is unlocked.

16.2.2 The Problem: Locks Alone Do Not Guarantee Conflict Serializability

Here is the crucial failure mode, and it is the reason this topic deserves care: just using shared and exclusive locks is not enough. The schedule that plain locking permits can still be non-conflict serializable.

Worked example — the schedule that slips past plain locking. Two transactions, $T_{1}$ and $T_{2}$ , operate on two accounts $A$ and $B$ , with $A = 100$ and $B = 200$ . $T_{1}$ transfers ₹50 from $B$ to $A$ . $T_{2}$ displays the total $A + B$ .

$T_{1}$ : lock-X(B); read(B); B := B − 50; write(B); unlock(B); lock-X(A); read(A); A := A + 50; write(A); unlock(A).

$T_{2}$ : lock-S(A); read(A); unlock(A); lock-S(B); read(B); unlock(B); display(A + B).

Now interleave them exactly as follows — every lock request is compatible, so plain locking lets the whole schedule through:

Step	$T_{1}$	$T_{2}$	Values on disk / in memory
1	lock-X(B) — granted		B = 200
2	read(B); B := 200 − 50 = 150		B (memory) = 150
3	write(B); unlock(B)		B = 150
4		lock-S(A) — granted (no one holds A)
5		read(A) → A = 100
6		unlock(A)
7		lock-S(B) — granted (B is now unlocked)
8		read(B) → B = 150
9		unlock(B)
10		display(A + B) → 250
11	lock-X(A) — granted
12	read(A); A := 100 + 50 = 150; write(A); unlock(A)		A = 150

Final answer: $T_{2}$ displays 250, but the correct total is 300. Sense-check: a serial run of $T_{1}, T_{2}$ (or $T_{2}, T_{1}$ ) always prints 300, because by the time the total is computed, both the debit and the credit have happened. The interleaved run shows a world that no serial run could produce — 100 + 150 mixes the state before and after the transfer.

Why does the conflict graph condemn this schedule? When we check for conflicting operations, we find two:

$T_{1}$ writes $B$ and $T_{2}$ reads $B$ — a read–write conflict on the same item, ordering $T_{1} \to T_{2}$ .
$T_{2}$ reads $A$ and $T_{1}$ writes $A$ — another read–write conflict on the same item, ordering $T_{2} \to T_{1}$ .

The two edges point in opposite directions, forming a cycle $T_{1} \to T_{2} \to T_{1}$ . Under conflict serializability theory, that schedule is not equivalent to a serial one; it is not conflict serializable, and it must not be allowed. Yet nothing in the plain shared/exclusive locking mechanism stops it: the schedule goes through, every lock request is compatible, and the unsafe interleaving executes anyway. The root cause, visible in the trace: $T_{1}$ released $B$ before its transaction finished, and $T_{2}$ released $A$ before its transaction finished — so each transaction could read an item that the other was still in the middle of changing.

The professor's blunt conclusion (preserved verbatim in spirit). Just blocking an item and refusing access is not sufficient. Locking a database item and refusing access is not, by itself, conflict serializability. A schedule can satisfy every lock request and still violate the guarantees. Since the engine cannot look at the whole schedule ahead of time, it needs a lock discipline that makes unsafe schedules impossible — something must be added on top of locking.

16.2.3 Student Question: Does Locking Not Already Protect ACID?

Q: When we lock an item for updates or reads, aren't we already preventing a violation of the ACID properties? Why are we saying that just implementing locks does not achieve a conflict serializable schedule? A: Two separate things are being mixed. First, is locking itself "ACID"? Locking is a mechanism for ordering access — it is not itself the ACID guarantee. Atomicity means everything or nothing: a transaction is an indivisible set of instructions, and if a transaction requests an exclusive lock on an item and the request is denied, the instruction does not execute; it waits until the lock is released, even if the transaction arrived earlier. The lock delays the time at which access happens, nothing more. Second, the real problem: we want many transactions to execute simultaneously, and they arrive on the fly, one after another, with no way to know in advance what the whole interleaving will look like. At the implementation level we need a mechanism that, at each moment, decides allow or not allow for the next instruction. Locks provide exactly that decision point — but the decision "grant the lock" is based only on the state of that one item. Nothing about the local decision checks whether the global schedule stays conflict serializable. That is why locking alone is insufficient and a discipline (like two-phase locking) must be layered on top.

The distinction to hold onto: a local rule (per-item lock compatibility) versus a global property (the whole schedule being conflict serializable). The worked example above is the proof that the local rule does not imply the global property.

16.2.4 Student Question: Foreign Keys, Granularity, and Cascade Deletes

Q: Suppose we have a foreign key relationship — say department and employee — where one department's data is accessed by a hundred people, and someone locks the department's primary key, and there is a cascade delete involved. How does locking handle that? A: This is about granularity. We are locking a single data item $Q$ , not the entire database schema, not an entire relation. The database has multiple levels of granularity: we can lock the whole relation or lock one particular data item inside that relation. The discussion here works at the level of a single relation where multiple people want to change multiple attributes, and one attribute is locked shared or exclusive. The concern about primary key and foreign key dependencies is valid but out of scope at this level: if the primary key is deleted and a cascade delete follows, there are multiple levels of dependency. The working assumption in this course is that the database software handles referential integrity — when we write a foreign key value it must exist as a referenced primary key, and when we delete a primary key with a cascade delete, we let the database software make those changes happen. We do not worry about locking across two different relations, one's primary key being another's foreign key. That is simply not the level this session is concerned with.

The useful distinction this answer teaches: locking granularity (tuple vs attribute vs page vs relation) is a separate design dimension from the locking protocol. Real engines support multiple granularities with intention locks — a subject this course deliberately defers. What matters here: the item $Q$ being locked is a single data item inside one relation, and referential-integrity machinery (foreign-key checks, cascade deletes) is the DBMS's job, not the lock protocol's.

16.2.5 Student Question: Main Memory vs Disk — What Does the Other Transaction Actually See?

Q: In the example, transaction $T_{1}$ holds an exclusive lock but it is making changes to $B$ . When $T_{2}$ acquires a shared lock and reads $B$ , will $T_{2}$ see the change $B = B - 50$ , even though $T_{1}$ has not made the change permanent? A: Yes — and this is exactly the right question to ask. The assumption is that the data items $A$ and $B$ are pulled from the hard disk (secondary storage) into the main memory, and the processor executes against main memory. There is a single processor with access to that main memory, and whenever a change is made to a data item in main memory, that changed value is visible to the processor. Durability is a separate matter: the changes are not permanent until they are written back to the hard disk. If a failure occurs before the write-back, the change is lost; on restart the data item is back to its disk value. But between two running transactions, the changed value is there.

Q (follow-up): So when $T_{2}$ reads $B$ , does it get $B = B - 50$ ? A: Yes. Initially $B$ is 100, stored permanently in secondary storage. It is brought into a frame in main memory, and $B$ 's value there is what transactions execute on. When $T_{1}$ changes it, the value in main memory becomes 50 ( $100 - 50$ ), and that is what $T_{2}$ reads. Before anything is made permanent, the value must be written back to the hard disk — otherwise a failure means it does not persist.

Worked example — memory value vs durable value. Say $B = 100$ on disk.

$B$ is fetched into a main-memory frame: memory $B = 100$ , disk $B = 100$ .
$T_{1}$ (holding the exclusive lock) executes $B := B - 50$ : memory $B = 50$ , disk $B = 100$ .
$T_{2}$ reads $B$ under a shared lock: it sees 50 — the main-memory value, because that is where execution happens.
A crash occurs before the write-back: memory vanishes, disk still holds 100. On restart $B = 100$ , and $T_{2}$ 's read of 50 is gone as if it never happened.
If instead $T_{1}$ commits and the buffer is written back, disk $B = 50$ — durable.

Final answer: concurrent transactions see the main-memory image (50); permanence comes only from the disk write-back. Sense-check: "visible now" and "permanent later" are two different guarantees — visibility is a main-memory fact, durability is a secondary-storage fact.

This is also the seed of the dirty read problem (section 16.5): $T_{2}$ read a value that later vanished. Locks that are released before commit are what allow this to happen; holding exclusive locks to commit is what prevents it.

16.2.6 Deadlock Under Plain Locking

There is a second failure mode on top of the serializability one: deadlock. Suppose $T_{1}$ has acquired an exclusive lock on $A$ and requests an exclusive lock on $B$ ; $T_{2}$ has acquired an exclusive lock on $B$ and requests an exclusive lock on $A$ . $T_{1}$ 's request is not granted because $T_{2}$ has not released $B$ ; $T_{2}$ 's request is not granted because $T_{1}$ has not released $A$ . Neither can proceed — neither releases, neither advances.

Worked example — the two-transaction circular wait.

Step	$T_{1}$	$T_{2}$	Why it happens
1	lock-X(A) — granted		nobody holds A
2		lock-X(B) — granted	nobody holds B
3	lock-X(B) — denied: waits		$T_{2}$ holds B
4		lock-X(A) — denied: waits	$T_{1}$ holds A

Both transactions are now frozen: $T_{1}$ waits for $T_{2}$ , $T_{2}$ waits for $T_{1}$ . No lock will ever be released — each is waiting for the other's release before it can proceed. Final answer: this is a deadlock; the only ways out are aborting one transaction (its locks are released, the other proceeds) or prevention by protocol. Sense-check: draw the wait edges $T_{1} \to T_{2}$ (" $T_{1}$ waits for $T_{2}$ ") and $T_{2} \to T_{1}$ — a two-node cycle; a cycle of waits is exactly the signature of deadlock.

This is the classic deadlock condition of circular wait, and it can arise under locking even when every individual grant was legal. The four necessary conditions in the OS formulation map one-to-one: mutual exclusion (a lock is exclusive), hold-and-wait (each holds one item while waiting for another), no preemption (locks cannot be forcibly taken), and circular wait (the two-node cycle).

So plain locking has two distinct problems: (1) it can allow schedules that are not conflict serializable, meaning the ACID properties can be compromised — a failure at the wrong moment can leave something non-persistent or inconsistent; and (2) it can deadlock — a situation that, under plain locking, "was not even occurring here; neither this may proceed, neither that may proceed."

16.2.7 The Problem-First Teaching Method

Q: Thank you — so what is the solution? Tell me the solution, I am not here for problem after problem. A: The problem itself needs to be acknowledged first. Unless we understand the gravity of the problem and its root cause, we cannot design the solution — and once the root cause is understood, the same solution generalizes and can be reapplied. The chain of reasoning is: we want multiple transactions to execute simultaneously, because concurrent access gives better response time and a busier processor. Transactions keep arriving on the fly. We are using a lock-based protocol to manage them. And the lock-based protocol, while managing them, is giving the problem that it does not restrict us to conflict serializable schedules and may still violate ACID. Now the solution: impose a discipline on when locks may be acquired and released — that is exactly the two-phase locking protocol.

The method is itself the lesson: naming the root cause first — lock grants are local, but schedule safety is global — makes the solution look obvious once stated, and the same pattern of reasoning reapplies to every subsequent protocol (strict 2PL, rigorous 2PL, timestamps). The root cause here: nothing stops a transaction from releasing a lock while it still needs the item, or from acquiring a lock after it has released one.

Recap + bridge. Locks give the engine a per-item decision point — shared and exclusive modes, compatibility as a matrix — but the local rule alone admits non-conflict-serializable schedules (the ₹250 example) and deadlocks (the circular wait). Both failures trace to the same freedom: transactions may release and re-acquire locks at any time. The next section's two-phase locking protocol is precisely the discipline that removes that freedom, and its stricter variants remove the two failure modes one by one.

Where this matters in the field: real engines expose this exact distinction — MySQL InnoDB and PostgreSQL lock rows with shared/exclusive modes, and their isolation guarantees (sections 16.5) are implemented by choosing when locks are released, not by inventing new lock kinds. The ₹250 banking trace is the reason every database manual warns against releasing locks mid-transaction.

16.3 Two-Phase Locking (2PL)

16.3.1 Growing Phase, Shrinking Phase, and the Lock Point

The basic idea is a single, stark rule: a transaction's locking life is divided into two phases, and the phases never overlap.

Growing phase: the transaction may acquire locks, but may not release any lock.
Shrinking phase: the transaction may release locks, but may not acquire any more.

The lock point is the moment when the transaction has acquired all the locks it will ever need — the boundary between the phases. Once the first lock is released (shrinking begins), acquiring any further lock is strictly forbidden. The schedule that motivated the problem — release a lock, then later acquire another one — is precisely what 2PL makes illegal. Any transaction that releases and then re-acquires is violating the rule; a lock requested after the transaction started shrinking is denied, and the requesting transaction waits. The rule is captured as: keep acquiring locks; as soon as you start releasing, you can never acquire again.

Why the two phases guarantee conflict serializability. The proof sketch runs through the lock point. The lock point of a transaction is the moment it holds its final lock; from then on it only releases. For any two transactions $T_{i}$ and $T_{j}$ , whichever reaches its lock point first holds all its locks while the other is still growing — and every conflicting operation on a shared item must be ordered by the locks. Concretely: if $T_{i}$ reaches its lock point before $T_{j}$ , then any conflict between them (say a read of $X$ by $T_{j}$ after $T_{i}$ wrote $X$ ) is forced to occur in $T_{i}$ -before- $T_{j}$ order, because $T_{i}$ never released $X$ before its lock point. Ordering the transactions by lock-point time therefore yields a serial order that matches every conflict edge — a cycle-free precedence graph. That is the textbook argument: 2PL permits only conflict serializable schedules (R1 §18.1.3; T1 §22.1).

Worked example — the rule applied to the failing schedule of 16.2.2. Re-run the ₹50 transfer ( $T_{1}$ ) and the total display ( $T_{2}$ ) from the previous section, now under 2PL — every lock held until the transaction's last access:

$T_{1}$ : lock-X(B); read(B); B := B − 50; write(B); lock-X(A); read(A); A := A + 50; write(A); unlock(B); unlock(A).

$T_{2}$ : lock-S(A); read(A); lock-S(B); read(B); unlock(A); unlock(B); display(A + B).

The formerly unsafe interleaving is now impossible. If $T_{1}$ starts first, it holds both $B$ and $A$ in exclusive mode until its final accesses, so $T_{2}$ cannot read either account until the transfer is complete — the display necessarily sees $A = 150$ , $B = 150$ , total 300. If $T_{2}$ starts first, it reads both accounts before $T_{1}$ moves — again a consistent 300. Final answer: under 2PL every allowed interleaving prints 300, matching the serial results. Sense-check: 2PL did not change what the transactions compute; it removed the window in which one transaction could observe the other half-finished — which is exactly what conflict serializability requires.

Note that the lock point argument works even though the unlock statements need not sit at the very end of the transaction — the only requirement is that no acquire follows the first release. A transaction may release one item early and then keep working on items it still holds, as long as it never requests another lock.

16.3.2 Strict Two-Phase Locking

The strict two-phase locking protocol tightens the rule for one kind of lock: a transaction must hold all its exclusive locks until it commits (or aborts). The transaction still acquires locks during its growing phase and may release shared locks once it starts shrinking — but an exclusive lock can only be released at commit or abort. The point of the asymmetry: if a transaction writes an item and then releases the exclusive lock before committing, another transaction can read the written-but-uncommitted value; if the writer then aborts, the reader has read a value that never existed. Holding exclusive locks to the end prevents that entire class of problem.

The failure strict 2PL closes — cascading rollback. Under plain 2PL, consider: $T_{5}$ writes $A$ and releases its exclusive lock, then $T_{6}$ reads $A$ , writes $A$ , releases, and $T_{7}$ reads $A$ . If $T_{5}$ now fails and rolls back, $T_{6}$ must roll back too (it read and rewrote $T_{5}$ 's vanished value), and then $T_{7}$ must roll back (it read $T_{6}$ 's). A single failure drags a chain of transactions down with it — an avalanche of rollbacks (R1 §18.1.3). Strict 2PL cuts the chain at its root: the exclusive lock on $A$ stays with $T_{5}$ until commit or abort, so no other transaction can ever read the uncommitted value — there is nothing to cascade. This is why the standard texts state the guarantee as: strict 2PL ensures conflict serializability and recoverability/cascadelessness (R1 §18.1.3; T1 §22.1).

16.3.3 Rigorous Two-Phase Locking

The rigorous two-phase locking protocol is stricter still: the transaction must hold all its locks — shared and exclusive — until it commits. There is no shrinking phase at all. The transaction grows its lock set, commits, and at the commit point releases everything at once. No lock is released anywhere in between.

The three protocols in one sentence each (the professor's summary):

Simple 2PL — acquire as much as you want, but after the first release you may never acquire again;
Strict 2PL — same, except exclusive locks stay held until commit or abort (shared locks may be released during shrinking);
Rigorous 2PL — nothing is released until commit; growing phase, then commit, then release everything.

One extra consequence of rigorous 2PL worth noting: because nothing is released until commit, transactions can be serialized in their commit order — the commit sequence itself is a valid serial order (R1 §18.1.3).

16.3.4 Student Question: May Read/Write Operations Sit Between Lock Statements?

Q: In rigorous two-phase locking, should one not have read and write operations interspersed between lock statements? In $T_{1}$ there is a write $B$ , then a read — but you have not acquired all the locks at the very beginning, like lock exclusive $A$ at the start itself. Can you have write, read, write interspersed between lock statements? A: Yes, you can — the locks do not all have to be acquired up front. The protocol says nothing about when you acquire locks, only about when you release them. You keep working: acquire lock on $A$ , read or write, later realize you need $B$ , acquire the lock on $B$ — if it is granted, continue; if not, you wait there. Read and write operations may be interspersed with lock acquisitions freely. What is forbidden is releasing. In rigorous 2PL, until you commit you cannot release any lock, whatever you do in between.

Student's confirmation: So a lock acquisition can be interspersed, but the unlock happens only at the end. Correct.

The takeaway that removes a common misunderstanding: the "two phases" describe lock acquisitions vs lock releases, not reads vs writes. A transaction can read, write, lock, read, lock, write — an arbitrary mix — as long as no release happens before the last acquisition.

16.3.5 Why the Variants Exist: Recoverability, Cascading Rollback, Deadlock Freedom

Each variant exists for one of three concrete safety reasons, and the progression from simple to strict to rigorous is driven by them:

ACID. The baseline requirement: only conflict serializable schedules may execute, so the ACID properties hold.
Recoverability. A schedule is recoverable if every transaction that reads something written by another transaction commits only after that other transaction commits. If I read a value written by $T_{2}$ , then I commit, and then $T_{2}$ fails and rolls back — I have committed using data that has since disappeared. That is not allowed. If I read something written by another transaction, that transaction must commit first.
Cascading rollback freedom. Related but stricter: no transaction may read an uncommitted value at all. When a transaction rolls back, the failure must not ripple through other transactions that read its data, forcing them to roll back too, and those that read from them, and so on — an avalanche of rollbacks. Strict and rigorous 2PL guarantee this by never releasing exclusive locks before commit.
Deadlock freedom. The protocols must also avoid or handle the circular-wait deadlocks described earlier.

None of these is free: the stricter the release discipline, the longer locks are held and the more waiting occurs. That is the reason there is a spectrum of protocols rather than a single one — "everyone has its own advantages, strengths, and they are there for certain reasons."

Exam note: the cost–benefit ladder. Basic 2PL buys conflict serializability at the cost of possible dirty reads and cascading rollbacks. Strict 2PL adds recoverability/cascadelessness at the cost of holding exclusive locks longer (less concurrency). Rigorous 2PL adds full isolation until commit at the cost of the longest waits. The ladder mirrors the normalization discussion (BCNF vs 3NF): each stricter rung buys a property, and nothing is free.

16.3.6 The Lock Manager and Lock Table

At the implementation level, who enforces all this? A lock manager component of the database management system. It maintains a lock table, which records, for the whole system: which transaction has locked which data item, which kind of lock (shared or exclusive) is held, and which transactions are waiting for which items. Every lock request and release goes through the manager, which consults the table, grants or queues the request, and updates the records. The lock manager is the physical machinery that turns the logical 2PL rules into enforced behavior — "things need to work in a different way" than transactions simply helping themselves.

Anatomy of a lock-table record. For a shared/exclusive scheme the lock manager typically stores four fields per locked item: the data item name, the lock mode (read-locked or write-locked), the number of current readers (for a read-locked item; for a write-locked item, the single holding transaction), and the queue of waiting transactions. The lock manager also implements the compatibility matrix: a shared request succeeds while the item is read-locked (incrementing the reader count), an exclusive request succeeds only when the item is unlocked, and every incompatible request joins the waiting queue, to be awakened when the item's readers drain or the writer unlocks (T1 §22.1).

16.3.7 Deadlock Handling: Wait-Die, Wound-Wait, Wait-For Graphs

Deadlocks can still happen under 2PL (a transaction may hold some locks, wait for another, while the other waits back). The session names the standard handling strategies — wait-die and wound-wait — and the wait-for graph, and explicitly marks them as self-study: the session presents them as known tools but does not drill into them. The connection is drawn across courses, and it is exact:

Real-world: the wait-for graph is the same structure as the resource allocation graph (RAG) taught in operating systems, and the same idea recurs in advanced operating systems, distributed systems, and cloud computing. Only the labels change: in an OS the vertices are processes and the resources are devices or memory; in a database the vertex is a transaction and the resource is a conflicting operation on a data item. The deadlock-detection algorithms are identical. Anyone who has studied the OS version already knows this material — "exactly the same thing. Nothing different."

Q: Are we going to learn deadlock detection and its solution with the wait-for graph in this course? A: No — not in this particular course. Deadlock detection and recovery via wait-for graphs are left for self-study; the topic comes up again in several other courses. There are ways to detect a deadlock (by finding a cycle in the wait-for graph) and to resolve it, but the main point of this course is the concurrency-control protocols themselves. Deadlock handling appears as a part of it and is important, which is why it is mentioned — but it is not the focus.

Exam note: the course treats wait-die, wound-wait, and the wait-for graph as named tools you should recognize and be able to connect to the OS material — full coverage appears in sections 16.6 and 16.7 of these notes as syllabus supplements, but the professor explicitly does not examine them in depth here.

16.3.8 Student Question: Locking Happens in Main Memory

Q: The lock prevention or the scheduling we are doing now — this happens only in the main memory, right? It is not on the hard disk, right? A: Right. Think about where the transactions come from: there is a server, an application running on it, and many people using the application through their browsers and phones. The goal is to protect the database itself — keep it consistent, keep it unhurt. The database management system handles access protection for different transactions either at the lock level or at the transaction level. At the lock level it says: no one else may hold the lock — not at the physical or secondary storage level, and not even at the main memory level; nobody is allowed to change the item even in main memory. In practice, when a transaction accesses a data item, the item is moved from secondary storage into a main memory frame and the changes happen there. A change made to the main-memory image is treated as if it were made directly in the secondary storage, which is exactly why the main-memory image is protected by locks as well. All of this locking and scheduling activity happens in the main memory — and the reason is the storage hierarchy: because of cost efficiency, we do not perform every change directly in secondary storage; working on the main-memory copy emulates the direct change.

The storage-hierarchy punchline: disk is cheap but slow, main memory is fast but costly — so data is staged in memory, changed there, and written back. Locks therefore guard the in-memory image (the only place execution happens), which is why an exclusive lock blocks even an in-memory change by another transaction.

Recap + bridge. Two-phase locking is the discipline layered on top of plain locks: growing phase (acquire only), lock point, shrinking phase (release only). Simple 2PL guarantees conflict serializability; strict 2PL adds recoverability by holding exclusive locks to commit; rigorous 2PL holds everything to commit. The enforcement machinery is the lock manager and lock table, and the remaining dangers are deadlock (handled by wait-die, wound-wait, or the wait-for graph — self-study) and the concurrency anomalies, which strict variants already begin to close. The next major mechanism attacks the same problem from a different angle: no locks at all, only timestamps.

Where this matters in the field: every commercial engine implements one of these rungs — MySQL InnoDB's default uses strict-2PL-style holding of exclusive locks to commit, with next-key locks (a later topic) layered on top; PostgreSQL uses a variant of 2PL with lock modes matching the shared/exclusive matrix. When a deadlock error message appears ("deadlock detected, transaction rolled back"), it is this section's machinery doing its job.

16.4 The Timestamp-Based Protocol

16.4.1 The Token Number Analogy

Hook — why would anyone drop locks? Locks make transactions wait, and waiting creates deadlocks. What if transactions could never wait at all — accepted or rejected instantly? The token-number system of everyday life shows how: decide everything by who arrived first.

Before the mechanics, the intuition. Consider two kinds of food outlets. A large chain — say Domino's — hands every customer a token number the moment they enter. You know that within 15–20 minutes your number will be displayed, you collect, you eat. The experience is predictable. Now a small kiosk run by genuinely excellent cooks: as soon as an order is cooked, it is served — no tokens, no numbers. What happens under load? A long queue, and chaos: people do not know when their order will come, how long it will take, or who is served first and second. The same chaos appears in hospitals, pilgrimages, banks — anywhere the order of service is unclear — and the token system fixes it by making the order explicit: first order is mine, second is yours, third is his. The token number encodes seniority: who came first and who came second.

Real-world: the token system is the everyday ancestor of the timestamp-based protocol. Every transaction that arrives is handed a transaction number, and that number is the time at which it arrived. The session even pushes the analogy to family and hierarchy: an elder brother has a higher responsibility, so his mistakes are punished more harshly than a younger sibling's; a parent must be tolerant and absorb the mistakes of the child; a professor in a high-responsibility position cannot cut corners the way a student can. In the timestamp protocol, the transaction that came first carries the more senior timestamp and bears the corresponding responsibility — and the punishment for missing its turn is severe.

Where the analogy breaks. The token system never rolls anyone back — every customer eventually eats. The timestamp protocol does roll back transactions that miss their turn (their work is discarded and restarted). Seniority is used as a strict ordering rule, not a queue; a senior transaction that arrives too late for a data item is not served late — it is rejected outright. The family analogy's "harsher punishment" is exactly this: the senior's mistake costs the whole transaction.

16.4.2 Transaction Timestamps and Data Item Timestamps

The mechanics: assume a clock assigns numbers (for teaching, 1, 2, 3; in reality, milliseconds or microseconds). When a transaction first gets access to the processor — its "birth" — it receives a timestamp, and no two transactions can enter the processor at the same time, so timestamps are unique. $T_{1}$ enters at time 3, so $T S (T_{1}) = 3$ ; $T_{2}$ enters later at time 6, so $T S (T_{2}) = 6$ . The transaction timestamp is fixed forever: "you cannot change the time at which you are born." Whatever wall-clock time passes, the transaction keeps working with the same timestamp — if $T_{1}$ performs an operation at time 15, its timestamp is still 3.

Intuition — the crucial subtlety, stated once and used everywhere. The timestamps recorded on a data item are the timestamps of the transactions that accessed it, not the wall-clock time at which the access happened. If a read happened at wall-clock time 15 but the reader was $T_{1}$ with timestamp 3, then $R (Q)$ becomes 3. The item's stamps record who accessed it last in the seniority order — not when. This is the professor's "you cannot change the time at which you are born" moment: seniority is set at birth and never changes, even as the clock keeps ticking.

Every data item $Q$ carries two timestamps of its own:

$R (Q)$ — the read timestamp of $Q$ : the largest timestamp of any transaction that read $Q$ . It is updated to $R (Q) \leftarrow max (R (Q), T S (T))$ after each allowed read.
$W (Q)$ — the write timestamp of $Q$ : the largest timestamp of any transaction that wrote $Q$ . It is updated to $W (Q) \leftarrow T S (T)$ after each allowed write.

The smaller the timestamp, the older (more senior) the transaction: $T_{1}$ with $T S (T_{1}) = 3$ is senior to $T_{2}$ with $T S (T_{2}) = 6$ , because $T_{1}$ arrived first. This matches the reference treatment exactly: timestamps are assigned in the order transactions start, so $T S (T_{1}) < T S (T_{2})$ means $T_{1}$ began first (T1 §22.2.1).

When a transaction $T_{i}$ with timestamp $T S (T_{i})$ requests an operation on $Q$ , the engine compares $T S (T_{i})$ against $R (Q)$ and $W (Q)$ . The comparisons encode one idea: a junior transaction (higher number = came later) must never be disturbed by a senior transaction that missed its turn.

16.4.3 The Read Rule

When $T_{i}$ requests a read of $Q$ :

If $T S (T_{i}) < W (Q)$ — a transaction that came later has already overwritten $Q$ . The value $T_{i}$ wants to read no longer exists; the read is rejected, and $T_{i}$ rolls back entirely.
Otherwise the read is allowed, and $R (Q)$ is updated to the maximum of its current value and $T S (T_{i})$ .

The read rule, formalized (reconciled with the standard treatment in T1 §22.2.2, which checks write_TS(X) > TS(T)):

$On read of Q by T_{i} : if T S (T_{i}) < W (Q) : reject the read; roll back T_{i} otherwise: allow the read; R (Q) \leftarrow max (R (Q), T S (T_{i}))$

Only the write timestamp is checked for a read. A senior transaction reading an item that a junior has already overwritten is reading a value that no longer exists — the senior's turn to see the old value is gone. The read timestamp is not checked on reads (reads never conflict with reads) — it is only updated after a successful read.

The plain-language statement from the session, preserved as the audit trail: "if the read timestamp of A is less than or equal to the timestamp of the transaction which wants to read, it's OK. Otherwise it is not a good one" — the comparison in question being the transaction's timestamp against the item's write timestamp; and later, more precisely: "when I am reading any data item B, I will check: is my timestamp less than the write timestamp of B? If it is less than, I will have to roll back." For a read, only the write timestamp is checked; the read timestamp is only updated after a successful read.

Worked example — the story version. $T_{1}$ (timestamp 3) and $T_{2}$ (timestamp 6) both want a seat. $T_{2}$ writes the data item $A$ — $W (A)$ becomes 6. Now $T_{1}$ wants to read $A$ : its timestamp 3 is less than $W (A) = 6$ , which means someone who came later than $T_{1}$ has already overwritten the value $T_{1}$ meant to read. $T_{1}$ missed its opportunity — the read is rejected and $T_{1}$ rolls back. Final answer: a senior transaction may never read a value written by a junior. Sense-check: if the seat's final state was produced by $T_{2}$ , a senior $T_{1}$ reading an older state would act on stale information — the protocol prefers to discard $T_{1}$ 's work.

16.4.4 The Write Rule

When $T_{i}$ requests a write of $Q$ , both timestamps are checked:

If $T S (T_{i}) < R (Q)$ — a transaction that came later has already read $Q$ . $T_{i}$ was supposed to produce the value that transaction reads; since it failed to write in time, the junior transaction read whatever else was there. The write is rejected, and $T_{i}$ rolls back.
If $T S (T_{i}) < W (Q)$ — a transaction that came later has already written $Q$ . The write is rejected, and $T_{i}$ rolls back.
Otherwise the write is allowed, and $W (Q)$ is updated to $T S (T_{i})$ .

The write rule, formalized (reconciled with the standard treatment in T1 §22.2.2, which checks read_TS(X) > TS(T) or write_TS(X) > TS(T)):

$On write of Q by T_{i} : if T S (T_{i}) < R (Q) or T S (T_{i}) < W (Q) : reject the write; roll back T_{i} otherwise: allow the write; W (Q) \leftarrow T S (T_{i})$

The one-line summary for remembering — the professor's mnemonic: "for reading I have to only check the write timestamp; for writing I have to check both the read timestamp and the write timestamp."

The punishment framing is deliberate: "you came first, you were allowed to write first, but you did not write. And the transaction came and rolled. Now you want to write? No, you are not allowed. You rolled back again." A rolled-back transaction is restarted — it takes its birth again — at a fresh, later timestamp (in the example, 17). Restarting with a new timestamp is what makes eventual progress possible: the restarted transaction is now the most senior and will not be rejected by the same conflicts.

Scope — why restart uses a "new" timestamp here, unlike wait-die/wound-wait. In the timestamp protocol, the rolled-back transaction is reincarnated with a fresh, later timestamp — because its old (smaller) timestamp is precisely what caused its rejection; replaying with the same timestamp would reproduce the identical rejection forever. This contrasts sharply with the wait-die/wound-wait schemes of section 16.6, where a restarted transaction keeps its original timestamp so it eventually grows old enough to win (T2 §17.4.1 and T1 §22.1.5). Two uses of "timestamp," two restart policies — the exam-relevant distinction (T2 §17.6.2 makes exactly this point).

16.4.5 Worked Example: The Complete Read-Write Walkthrough

The full worked example, step by step, exactly as presented:

Setup. $T_{1}$ is born at timestamp 3 and issues a write to $A$ . The item's timestamps become $R (A) = 3$ , $W (A) = 3$ (the transaction that read and wrote is $T_{1}$ , whose timestamp is 3). Later — at wall-clock time 11 — $T_{1}$ reads $A$ . Nothing changes: $R (A) = 3$ , $W (A) = 3$ , because the timestamps record the transaction's timestamp, not the time of the operation.

Now $T_{2}$ enters; its first operation executes at timestamp 12, so $T S (T_{2}) = 12$ .

Time	Operation	Check	Result
3	$T_{1}$ writes $A$	(fresh item)	$R (A) = 3$ , $W (A) = 3$
11	$T_{1}$ reads $A$	read checks only $W (A)$	allowed; stamps unchanged, $R (A) = 3$
12	$T_{2}$ reads $A$	is $12 < W (A) = 3$ ? No	allowed; $R (A) \leftarrow max (3, 12) = 12$
13–14	$T_{1}$ reads $A$ again	is $3 < W (A) = 3$ ? No (not strictly less)	allowed; $R (A) \leftarrow max (12, 3) = 12$
15	$T_{2}$ writes $A$	is $12 < R (A) = 12$ ? No. Is $12 < W (A) = 3$ ? No	allowed; $W (A) \leftarrow 12$
16	$T_{1}$ writes $A$	is $3 < R (A) = 12$ ? Yes	rejected — $T_{1}$ rolls back
17	(restart)	$T_{1}$ is reborn	fresh timestamp 17

Final answer: $T_{1}$ 's write at 16 is rejected because a junior ( $T_{2}$ , ts 12) already read $A$ ; $T_{1}$ rolls back and is reborn at 17. Sense-check: $T_{1}$ was allowed to write $A$ first at its birth — it simply never wrote again until 16, and by then $T_{2}$ had read the item, so the value $T_{1}$ would have produced is no longer what anyone should see.

The lesson the walkthrough hammers: the check for a read is only against the write timestamp; the check for a write is against both. And every value is preserved exactly — 3, 11, 12, 13, 14, 15, 16, 17 — because the intermediate numbers are the entire point.

16.4.6 The Rules in Plain Language: Seniority, Not Write-Before-Read

When a student compressed the rule as "any transaction should not write before reading," the instructor corrected the framing — the rule is not about ordering read before write inside a transaction. It is about seniority:

If I read an item, I must be reading a value written by me or by somebody senior to me (an earlier timestamp). I may not read a value written by a junior transaction that came later.
If I write an item, I must be the one who wrote it earlier, or read it earlier, or somebody senior to me must have read it earlier. I may not write if a junior has already read or written the item.

The three forbidden shapes (the professor's canonical list):

I read something that a junior wrote — forbidden (read rule).
I write something that a junior already read — forbidden (write rule, first check).
I write something that a junior already wrote — forbidden (write rule, second check).

The railway version: two people want seats on the same train. The one who entered first must see the booking status that the later entrant's purchase produced. If the later entrant bought the ticket and the earlier entrant is now trying to read the (updated) status — too late; the earlier transaction had its chance and must roll back. The same train, the same seat, the same data item — that is what makes it one transaction's business.

Q (a student re-stating the idea): We have not yet served a read request, and before serving it we are trying to update the item — the system assumes the value would never be produced, so it rejects it. Is that the idea? A: You are correct. Two people are doing something on the same booking system; each of their actions is a transaction — everything or nothing. If one person read the reservation status and the other, who entered first, then updates or purchases the ticket, the first one should be reading the updated status produced by the senior transaction. When the ordering comes out the other way — the senior missed its turn, the junior wrote — the senior must roll back rather than act on stale information.

16.4.7 Worked Example: Display, Read Timestamps, and the Ambiguity of "Reading"

A second schedule: $T_{1}$ has timestamp 1, $T_{2}$ has timestamp 2, and item $B$ is in contention. Assume $W (B) = W (A) = 0$ initially.

Step	Operation	Check	Result
1	$T_{1}$ reads $B$	is $1 < W (B) = 0$ ? No	allowed; $R (B) = 1$
2	$T_{2}$ reads $B$	is $2 < W (B) = 0$ ? No	allowed; $R (B) \leftarrow max (1, 2) = 2$
3	$T_{1}$ reads $A$	is $1 < W (A) = 0$ ? No	allowed; $R (A) = 1$
4	$T_{2}$ reads $A$	is $2 < W (A) = 0$ ? No	allowed; $R (A) = 2$
5	$T_{2}$ displays $A + B$	(see discussion: does display read?)	both item reads pass under the stated assumption
6	$T_{2}$ writes $B$	is $2 < R (B) = 2$ ? No. Is $2 < W (B) = 0$ ? No	allowed; $W (B) = 2$
7	$T_{1}$ reads $B$ again	is $1 < W (B) = 2$ ? Yes	rejected — $T_{1}$ rolls back

Final answer: $T_{1}$ 's second read of $B$ is rejected because $T_{2}$ (junior, ts 2) has already written $B$ — $T S (T_{1}) = 1 < W (B) = 2$ . Sense-check: $T_{1}$ already read $B$ once when it held value 1's version; the newer value belongs to $T_{2}$ 's world, and $T_{1}$ 's world has passed it by.

The student in the session confirmed the last step explicitly — "its timestamp is 1, which is less than 2, so it is not allowed" — and the instructor agreed. The subtlety worth keeping: the instructor's first pass assumed the display of $A + B$ counted as reading both items, and the final check shows why the assumption matters. If the problem's display does not involve reading, the analysis changes. The rule for answering: if there is any ambiguity about whether an operation involves reading, write the assumption down explicitly in your answer ("assuming that display involves reading"), and apply the rules consistently under that stated assumption.

Exam note: the display-read ambiguity is a named exam trap in this course. A question that says "display $A + B$ " may or may not intend two reads of $A$ and $B$ . State your assumption in the answer ("assuming that displaying involves reading $A$ and $B$ "), then apply the read rule consistently — and if you assume the display does not read, the timestamps of $A$ and $B$ simply are not updated by the display.

16.4.8 Worked Example: A Later Write Beats an Earlier Write

Same pattern for writes alone: $T_{1}$ has timestamp 1, $T_{2}$ has timestamp 2, item $Q$ in contention.

Step	Operation	Check	Result
1	$T_{1}$ writes $Q$	(fresh item)	allowed; $W (Q) = 1$
2	$T_{2}$ writes $Q$	is $2 < R (Q) = 0$ ? No. Is $2 < W (Q) = 1$ ? No	allowed; $W (Q) = 2$
3	$T_{1}$ writes $Q$ again	is $1 < R (Q)$ ? No. Is $1 < W (Q) = 2$ ? Yes	rejected — $T_{1}$ rolls back

Final answer: the senior $T_{1}$ 's second write is rejected because the junior $T_{2}$ has already written $Q$ . Sense-check: writing $Q$ after a junior wrote it is forbidden shape 3 — the value would be immediately overwritten by a newer one, so it is discarded and $T_{1}$ restarts.

The schedule is not conflict serializable — there are conflicting instructions (both transactions writing the same item in an interleaved order) — and the timestamp protocol rejects exactly the later instruction of the earlier transaction. This is the demonstration that the protocol refuses non-conflict-serializable schedules.

16.4.9 Worked Example: Five Transactions, Timestamps 1 to 5

The session's largest walkthrough. Five transactions have timestamps 1, 2, 3, 4, 5 (read as $T S (T_{1}) = 1$ , $T S (T_{2}) = 2$ , $T S (T_{3}) = 3$ , $T S (T_{4}) = 4$ , $T S (T_{5}) = 5$ ; all items start with $R = W = 0$ ). The operations, in order, with the analysis of each:

Step	Operation	Check	Result
1	$T_{1}$ reads $X$	is $1 < W (X) = 0$ ? No	allowed; $R (X) = 1$
2	$T_{2}$ reads $Y$	is $2 < W (Y) = 0$ ? No	allowed; $R (Y) = 2$
3	$T_{3}$ reads $Y$	is $3 < W (Y) = 0$ ? No	allowed; $R (Y) = 3$
4	$T_{4}$ writes $Y$	is $4 < R (Y) = 3$ ? No. Is $4 < W (Y) = 0$ ? No	allowed; $W (Y) = 4$
5	$T_{5}$ writes $Z$	(fresh item)	allowed; $W (Z) = 5$
6	$T_{1}$ reads $Z$	is $1 < W (Z) = 5$ ? Yes	rejected — $T_{1}$ rolls back
7	$T_{2}$ reads $Z$	is $2 < W (Z) = 5$ ? Yes	rejected — $T_{2}$ rolls back

Final answer: $T_{1}$ and $T_{2}$ both roll back after trying to read $Z$ , because the junior $T_{5}$ (ts 5) has already written it; $T_{3}$ and $T_{4}$ proceed. Sense-check: each rejection is the read rule firing — the senior's chance to read $Z$ 's older state ended the moment $T_{5}$ wrote it.

One number to be careful about: in step 5 the write is performed by $T_{5}$ , whose timestamp is 5, so $W (Z) = 5$ . (The session's narration slips once and says "four" while describing this step — the settled value is 5, the writing transaction's own timestamp.) The later rejections at steps 6 and 7 compare against $W (Z) = 5$ .

The procedure applied to every instruction, mechanically: for a read, compare the transaction's timestamp with the item's write timestamp; for a write, compare with both the read and write timestamps; reject and roll back on the first failing comparison.

Q: When the question gives timestamps, what are we supposed to assume — for example if the transactions are labeled $T_{1}$ through $T_{5}$ with timestamps 1 to 5? A: Whatever the question gives. If the question states the timestamps of $T_{1}, T_{2}, \dots$ outright, use those values; these timestamps have nothing to do with the actual clock time. When the question supplies different values — one variant mentioned gives $T_{1} = 5$ , $T_{2} = 6$ , and so on — you take the columns' timestamp values as given. The read and write timestamps recorded on a data item are the timestamps of the transactions that read and wrote it: if $X$ is read by the transaction with timestamp 5, then $R (X) = 5$ , not the wall-clock moment of the read.

Q: Is abort basically the same as rollback? A: Yes — when a transaction is aborted, it is rolled back, exactly the same thing. The transaction restarts with a fresh, later timestamp.

16.4.10 The Analogy That Clicks: Tokens, Birth Times, and Immutable Seniority

The two ideas to keep together. First, every transaction has a timestamp fixed at birth — the moment it first got processor access — and it keeps that timestamp for its whole life, no matter what wall-clock time elapses. Second, every data item carries the two stamps recording which transactions accessed it last; the item "updates who is the person — the best person who accessed me in reading or writing." The protocol then guarantees one thing: the serializability order is exactly the timestamp order. Transactions execute as if they ran in timestamp order, because any deviation (senior missing its turn) is caught at the instruction level and rolled back. This is what makes the timestamp protocol a non-waiting alternative to locking: no transaction ever waits for a lock — it is either allowed immediately or rolled back. There is no lock table, no wait-for graph, and consequently no deadlock — deadlock is impossible because no transaction ever waits for another.

The core contrast with locking, in one table:

Dimension	Lock-based protocol	Timestamp-based protocol
Ordering device	Locks acquired/released	Birth timestamps $T S (T_{i})$
When a conflict happens	Later transaction waits	Earlier transaction may be rolled back
Waiting	Yes — queues, wait-for graphs	No — allow or roll back immediately
Deadlock	Possible (needs handling)	Impossible by construction
Cost	Lock manager, lock table, waits	Timestamp maintenance, rollbacks/restarts

16.4.11 What the Timestamp Protocol Guarantees — and the Open Question

The session's closing analysis on the timestamp protocol: does it allow only recoverable schedules? Does it uphold ACID? Does it restrict to conflict serializable schedules? Does it reduce deadlock risk?

Conflict serializability: verified by demonstration. The schedule with the read of $B$ after $T_{2}$ 's write of $B$ — rejected. The schedule with the repeated write of $Q$ — rejected. The five-transaction schedule with the reads of $Z$ — rejected. In each case the rejected schedule had a conflict cycle, and the timestamp protocol let it through only after the unsafe instruction was rolled back. The protocol allows only conflict serializable schedules — "at least for this particular case," with the general argument that every conflict edge follows timestamp order, so cycles cannot survive.
Deadlock: eliminated structurally. Since no transaction ever waits, the circular wait that defines deadlock cannot form. The only waiting alternative — lock-based protocols — carries the deadlock risk.
Recoverability: the session raises the question ("does it allow recoverable schedules only?") and leaves it as the point to think through. The recorded material supplies the answer, and it is the one real weakness of basic timestamp ordering: basic TO does not guarantee recoverability. A rollback can cascade: if $T_{1}$ writes $A$ , $T_{2}$ reads $A$ and writes $B$ , and then $T_{1}$ rolls back, $T_{2}$ has used a value that has vanished — and must roll back too (T1 §22.2.2 calls this cascading rollback explicitly; T2 §17.6.2 shows an unrecoverable schedule permitted by the protocol). The standard fix is strict timestamp ordering: delay a conflicting operation until the transaction that wrote the item has committed or aborted — effectively simulating a lock on recently written items without ever forming a wait cycle. The conclusion to carry: timestamp ordering buys conflict serializability and deadlock freedom structurally, and recoverability must be bolted on via the strict variant.

16.4.12 How Much of the Course This Is

The session closes with calibration: the last 30–40 minutes are "the course in itself for timestamp or lock-based protocol" — the story spans three or four sessions of the course, and understanding it with meaning, not mechanically, is what makes practice possible. The study method endorsed: re-read the recorded sessions and practice on different transactions and schedules — apply a lock, release a lock, and observe what may happen and what may not. "Unless you do one or two problems, if a question comes across, you might stumble." Mechanical memorization without understanding will not survive an exam question; practicing after understanding is the only path.

Recap + bridge. The timestamp protocol is the token-number system made formal: every transaction is born with an immutable timestamp, every item remembers the timestamps of its last reader and writer, and every operation is judged against those stamps — reads against $W (Q)$ , writes against both $R (Q)$ and $W (Q)$ — with rollback as the only punishment. It guarantees conflict serializability by construction and eliminates deadlock structurally, at the cost of rollbacks and a recoverability gap that strict TO patches. The next sections harden this picture: the three classic anomalies the protocols prevent (16.5), the timestamp-based deadlock-prevention cousins wait-die and wound-wait (16.6), the wait-for graph (16.7), and Thomas' write rule, the classic optimization that makes the write rule less wasteful (16.8).

Where this matters in the field: timestamp ordering is the ancestor of modern non-locking schemes — snapshot isolation and optimistic concurrency control order transactions by version timestamps and validate conflicts instead of blocking. Postgres-style MVCC engines record "which version may this transaction see" using exactly this read/write-stamp logic, with old versions kept instead of rollbacks — the same seniority idea, gentler implementation.

16.5 Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom

Before the protocols, the syllabus asks for the three canonical ways concurrent execution can corrupt data — the anomalies that serializability testing and the protocols exist to prevent. Each one is a concrete, examinable failure story.

Hook. Every anomaly has the same skeleton: two transactions touch the same data item, and one of them gets to see or write a value it should never have seen. Learning the three skeletons by name is the cheapest exam insurance in this chapter.

A useful way to classify the skeleton: look at the conflict type between the two transactions' operations on the same item (the RR/RW/WR/WW taxonomy of R2 §16.2):

Conflicting operations	Anomaly it enables
Read → Read (RR)	None — reads never conflict
Read → Write (RW)	Inconsistent analysis (incorrect summary), nonrepeatable read
Write → Read (WR)	Dirty read (uncommitted dependency)
Write → Write (WW)	Lost update, dirty write

16.5.1 The Dirty Read (Temporary Update) Problem

The dirty read is exactly the disaster scenario of section 16.2.5 and the recoverability discussion of the previous session. Suppose $T_{1}$ writes data item $A$ , changing it from 100 to 50 in main memory, but has not yet committed — the change is temporary. $T_{2}$ reads $A$ and sees 50 — a value that has not been made permanent. Now $T_{1}$ fails and rolls back, restoring $A$ to 100. $T_{2}$ has read and acted on a value that never existed in the database — the "dirty" (uncommitted) data — and if $T_{2}$ computed or wrote anything based on 50, the database is now inconsistent. The name "temporary update problem" comes from the same story: $T_{2}$ observed an update that was only temporary. The fix is exactly the recoverability discipline of the earlier sessions — a transaction must never read a value written by an uncommitted transaction — and it is why the strict and rigorous 2PL variants hold exclusive locks to commit time.

Worked example — the full dirty-read trace.

Step	$T_{1}$	$T_{2}$	$A$ (memory)
1	write(A): A := 100 − 50		50 (uncommitted)
2		read(A) → sees 50	50
3		(acts on 50 — e.g. writes it somewhere)
4	FAILS and rolls back		A restored to 100

Final answer: $T_{2}$ read 50, a value that then vanished — the database is left with $T_{2}$ 's decisions based on data that never existed. Sense-check: everything $T_{2}$ derived from "50" is now wrong, because the durable truth is 100. The reference books call this the uncommitted dependency problem — $T_{2}$ became dependent on an uncommitted change (R2 §16.2).

16.5.2 The Incorrect Summary and Unrepeatable Read Problems

The unrepeatable read arises with committed updates. $T_{2}$ reads $A$ and sees 100. Meanwhile $T_{1}$ updates $A$ to 50 and commits. $T_{2}$ reads $A$ again and sees 50. The same transaction read the same data item twice and got two different answers — the read is not repeatable. Nothing was ever dirty; the problem is purely that $T_{2}$ 's view of the world changed mid-transaction. A report computed from a first read cannot be reconciled with a second read.

The incorrect summary problem is the aggregate version: a transaction computes a summary — say SUM over a column, the classic balance total across a set of accounts — while another transaction commits updates to the very rows being summed. The summarizer reads some rows at their old values and later rows at their new values, so the total corresponds to no consistent state of the database — it is a mixture of two different moments, and no serial execution could ever have produced it. Both problems are the isolation property failing, and both are prevented by locking the items a transaction reads for the whole transaction (so writers cannot change them) — which is precisely what strict 2PL, with its held-until-commit locks, delivers.

Worked example — the incorrect summary with real numbers (the classic R2 §16.2 trace). Three accounts hold 40, 50, 30. $T_{A}$ sums all three; $T_{B}$ transfers 10 from account 3 to account 1.

Step	$T_{A}$ (summarizer)	$T_{B}$ (transfer)	Values
1	read ACC1 → sum = 40		ACC1 = 40
2	read ACC2 → sum = 90		ACC2 = 50
3		read ACC3 = 30
4		update ACC3: 30 − 10 = 20 (commits)	ACC3 = 20
5		update ACC1: 40 + 10 = 50 (commits)	ACC1 = 50
6	read ACC3 → sum = 90 + 20 = 110

Final answer: $T_{A}$ prints 110 — but the true total is 120 (50 + 50 + 20). Sense-check: $T_{A}$ read ACC1 and ACC2 before the transfer and ACC3 after it, so its sum mixes two database moments; no serial order of the two transactions could produce 110. The same trace, viewed from $T_{A}$ 's own reads of one account: had $T_{A}$ read ACC1 twice, it would have seen 40 then 50 — the unrepeatable read in its simplest form.

16.5.3 The Phantom Read Problem

The phantom is the subtlest anomaly, and it defeats ordinary row locking. $T_{2}$ runs a range query — "all employees in department 5." $T_{1}$ concurrently inserts a new employee who belongs to department 5 and commits. $T_{2}$ runs the same range query again and sees a tuple that did not exist on the first run — a phantom tuple that appears between the two reads. The inserted row is brand new; no existing row was locked, modified, or deleted, so the locking protocol saw nothing to lock and could not have blocked the insert. Range queries need range protection: either the lock is on the index range itself (predicate locking, or gap/next-key locks on B+ tree index intervals), or the schedule is executed under a serializable isolation level that detects the phantom. The connection to the indexing sessions is exact: a B+ tree range scan over department 5 touches leaf intervals, and locking those intervals is how real engines (MySQL InnoDB's next-key locking, for example) stop phantoms.

Worked example — the phantom with real numbers. Employee table, one index on dept. Dept 5 has employees with salaries 40 and 60. $T_{2}$ : "SELECT AVG(salary) WHERE dept = 5" — locks the two leaf entries for dept 5, averages 50. Meanwhile $T_{1}$ inserts a new dept-5 employee with salary 100 and commits — the insert writes a different leaf page that $T_{2}$ never touched, so no lock conflict occurs. $T_{2}$ re-runs the same query: it now sees three rows, averaging 66.67.

Final answer: $T_{2}$ 's two runs answer 50 and then 66.67 for the "same" query — a phantom row appeared between the reads, and row-level locking could not have prevented it. Sense-check: locks protect existing rows; the phantom is a new row — the only way to stop it is to lock the gap in the index (the range where new rows could land), which is exactly what next-key/gap locking does (T2 §17.5.1 walks through this precise scenario).

Exam note — the anomalies are the SQL isolation levels in disguise. These three anomalies are not merely exam folklore — they are the formal content behind the SQL isolation levels. READ UNCOMMITTED allows all three, READ COMMITTED eliminates the dirty read, REPEATABLE READ adds the unrepeatable-read guarantee (and, in engines with next-key locking, the phantom), and SERIALIZABLE rules out all three — the very "isolation levels" the final session flagged as an old-paper topic.

Isolation level	Dirty read	Unrepeatable read	Phantom
READ UNCOMMITTED	possible	possible	possible
READ COMMITTED	prevented	possible	possible
REPEATABLE READ	prevented	prevented	prevented with next-key locking
SERIALIZABLE	prevented	prevented	prevented

Scope — what each anomaly's fix requires. The dirty read is closed by holding exclusive locks to commit (strict/rigorous 2PL) or by never reading uncommitted values (recoverability). The unrepeatable read and incorrect summary are closed by holding shared locks on read items until the transaction ends — so no writer can change a value the transaction already read. The phantom needs range-level protection — predicate locks or index gap locks — because no row lock can cover a row that does not exist yet. Matching each anomaly to its fix (property failed → protocol rule) is a standard exam question.

Where this matters in the field: the isolation-level list you choose in a real engine (SET TRANSACTION ISOLATION LEVEL ...) is a direct choice among these anomalies — PostgreSQL's REPEATABLE READ, for instance, prevents phantoms via its snapshot mechanism, while older engines without gap locking silently let phantoms through. When a financial reconciliation differs between two runs of the same query, an anomaly from this section — usually the unrepeatable read or the phantom — is almost always the culprit.

16.6 Deadlock Prevention: Wait-Die and Wound-Wait

Section 16.3.7 named wait-die and wound-wait as self-study; the syllabus requires them in detail, so this supplement gives the full treatment. Both are prevention schemes — they make deadlock structurally impossible, rather than detecting it after it happens — and both use the timestamp machinery of section 16.4. Every transaction gets a timestamp at birth; the older transaction (smaller timestamp) has higher priority.

Hook — the asymmetry that prevents deadlock. A cycle of waits needs at least one transaction that waits for another and is waited on in return. If the waiting rules make that impossible by age, deadlock can never form — no matter what the transactions do. Both schemes exploit exactly this: one of the two ages must always lose.

16.6.1 The Wait-Die Scheme (Non-Preemptive)

Wait-Die (non-preemptive). When transaction $T_{i}$ requests a lock held by $T_{j}$ :

If $T_{i}$ is older than $T_{j}$ ( $T S (T_{i}) < T S (T_{j})$ ), $T_{i}$ waits.
If $T_{i}$ is younger than $T_{j}$ , $T_{i}$ dies — it is aborted and restarted (with its original timestamp).

The scheme is non-preemptive because a transaction never steals a lock; it only waits or kills itself. "Die" is misleadingly named — the younger transaction does not terminate; it restarts and retries later.

16.6.2 The Wound-Wait Scheme (Preemptive)

Wound-Wait (preemptive). The mirror-image rules:

If $T_{i}$ is older than $T_{j}$ , $T_{i}$ wounds $T_{j}$ — $T_{j}$ is aborted and its lock released, and $T_{i}$ proceeds.
If $T_{i}$ is younger than $T_{j}$ , $T_{i}$ waits.

Wound-wait is preemptive: the older transaction takes the lock by force, aborting the holder.

16.6.3 Why Both Schemes Are Deadlock-Free

Why both schemes are deadlock-free — the one-line graph argument. A wait edge in the wait-for graph always points in one strict direction of age:

In wait-die, a transaction only ever waits on a younger transaction — so every wait edge points from older to younger. Following wait edges strictly decreases timestamps... no cycle can close.
In wound-wait, a transaction only ever waits on an older transaction — so every wait edge points from younger to older. Again strictly monotone, again no cycle.

More precisely (T1 §22.1.5): in wait-die, transactions only wait for younger transactions, so no cycle is created; in wound-wait, transactions only wait for older transactions, so no cycle is created. Circular wait — the one condition that defines deadlock — cannot form in either scheme.

The table worth memorizing:

Requesting transaction $T_{i}$ (versus lock holder $T_{j}$ )	Wait-die	Wound-wait
$T_{i}$ older than $T_{j}$	$T_{i}$ waits	$T_{i}$ wounds (aborts) $T_{j}$
$T_{i}$ younger than $T_{j}$	$T_{i}$ dies (aborts, restarts)	$T_{i}$ waits

16.6.4 The Trade-Offs and Starvation

Worked example — the same conflict, both schemes. $T_{1}$ (ts 1, older) holds a lock on $A$ . $T_{2}$ (ts 2, younger) requests $A$ , and later $T_{1}$ requests a lock on an item $T_{2}$ holds (say $B$ ).

Under wait-die: $T_{2}$ (younger) requesting $A$ from $T_{1}$ (older) → $T_{2}$ dies, restarts with ts 2. $T_{1}$ requesting $B$ from $T_{2}$ (younger) → $T_{1}$ waits (legal, since $T_{2}$ is younger). Every wait is old-waits-for-young; no cycle.

Under wound-wait: $T_{2}$ (younger) requesting $A$ from $T_{1}$ (older) → $T_{2}$ waits. $T_{1}$ (older) requesting $B$ from $T_{2}$ (younger) → $T_{1}$ wounds $T_{2}$ : $T_{2}$ aborts, releases $A$ , $T_{1}$ proceeds. Every wait is young-waits-for-old; no cycle.

Final answer: in both schemes the younger transaction is the one that gets aborted when a conflict involves age — and no waiting cycle ever survives. Sense-check: the age gradient on wait edges is the same trick as acyclic dependencies in a graph — monotone ordering forbids cycles by construction.

The trade-offs and the starvation question. Wait-die is gentler on data: a transaction that has all the locks it needs is never aborted (it is not requesting anything, so it never dies) — an advantage over wound-wait, where a long-running older transaction can wound and abort working younger transactions. But under wait-die, a young transaction can be killed repeatedly by an older one that keeps holding the item — starvation is possible in principle. Wound-wait aborts younger transactions aggressively, risking more wasted work, but guarantees older transactions never wait on younger ones — the token analogy of 16.4.1 ("the senior transaction's mistakes are punished") is exactly the wound-wait philosophy, carried from timestamps to locks. Both schemes avoid permanent starvation by restarting a transaction with its original timestamp: a repeatedly aborted transaction eventually becomes the oldest, hence the highest-priority, and gets everything it needs (T1 §22.1.5; T2 §17.4.1). Note the contrast with the timestamp protocol itself, where restarts take a new, later timestamp (section 16.4.4) — the two uses of timestamps must not be confused.

Recap + bridge. Wait-die and wound-wait convert the timestamp protocol's seniority into a lock discipline: older-waits (wait-die) or younger-waits (wound-wait) makes every wait edge point one way in age, so circular wait — and with it deadlock — cannot exist. Prevention is one strategy; the next section covers the opposite strategy: allow deadlock to happen, then detect and break it with the wait-for graph.

Where this matters in the field: prevention schemes appear where the cost of a detected-and-aborted transaction is unacceptable — specialized and distributed database systems, and lock managers with priority-based scheduling. Commercial engines default to detection (section 16.7) because deadlocks are rare in practice, but the same age-based priority logic powers wait queues in many schedulers.

16.7 Deadlock Detection and Recovery: The Wait-For Graph

Prevention avoids deadlock by construction; detection takes the opposite strategy — allow deadlock, then find and break it. The mechanism is the wait-for graph, which section 16.3.7 correctly identified as the database twin of the operating systems resource-allocation graph.

Hook. A deadlock is invisible until someone looks for it — the transactions themselves never complain; they just sit there, each waiting for a lock that will never be released. The wait-for graph is the x-ray that reveals the cycle.

16.7.1 Building the Wait-For Graph

Building the wait-for graph. Each transaction is a node. Whenever transaction $T_{i}$ is waiting for a lock held by transaction $T_{j}$ , draw a directed edge $T_{i} \to T_{j}$ (" $T_{i}$ is waiting for $T_{j}$ "). The graph is updated on every lock request, lock grant, and lock release. A deadlock exists if and only if the wait-for graph contains a cycle. The two-transaction deadlock of section 16.2.6 — $T_{1}$ holds $A$ , wants $B$ ; $T_{2}$ holds $B$ , wants $A$ — is the smallest possible cycle, $T_{1} \to T_{2} \to T_{1}$ . Longer cycles with three or more transactions are identical in structure: each transaction waits on the next, and the last waits back on the first.

Why a cycle means deadlock — and why a wait edge is not a precedence edge. A wait edge records a blocked transaction; a precedence (conflict) edge records a completed conflict. The textbook observation (T2 §17.4): if $T_{i}$ waits on $T_{j}$ and both eventually commit, the committed outcome contains a conflict edge the other way ( $T_{j}$ 's write precedes $T_{i}$ 's read). That link is why the wait-for graph is a live diagnostic while transactions are still running: a cycle in wait edges today means none of the transactions in the cycle can ever reach the operations that would break the cycle — none can commit.

Worked example — a three-transaction cycle. $T_{1}$ holds $A$ , waits for $B$ (held by $T_{2}$ ); $T_{2}$ holds $B$ , waits for $C$ (held by $T_{3}$ ); $T_{3}$ holds $C$ , waits for $A$ (held by $T_{1}$ ).

Nodes: $T_{1}, T_{2}, T_{3}$ . Edges: $T_{1} \to T_{2}$ , $T_{2} \to T_{3}$ , $T_{3} \to T_{1}$ . The walk $T_{1} \to T_{2} \to T_{3} \to T_{1}$ returns to its start — a cycle, therefore all three transactions are deadlocked. Final answer: none of $T_{1}, T_{2}, T_{3}$ can ever proceed; the system must abort one of them. Sense-check: removing any single edge would break the cycle — which is exactly why aborting one victim (releasing its locks) is sufficient to unfreeze the other two.

16.7.2 Detection: Finding Cycles

Detection. The database system runs a cycle-detection algorithm (a depth-first search of the graph) either periodically or when a transaction has waited too long. The choice of how often to check is itself a trade-off: frequent checks find deadlocks quickly but consume cycles; rare checks waste less detection effort but leave transactions waiting longer. In a cycle, every transaction in it is deadlocked — none can ever proceed.

16.7.3 Recovery: Victim Selection and Abort

Recovery. Breaking a cycle means picking a victim and aborting it. The victim selection rule is a cost decision: choose the transaction that is cheapest to sacrifice — the one holding the fewest locks, the one that has done the least work (fewest operations logged), the oldest or the newest by policy — and abort it, releasing all its locks. The released locks unblock the remaining transactions and the cycle is broken. The aborted transaction's work is undone through the standard rollback/log machinery of the recovery discussion, and it may be restarted. The exam-relevant contrast to keep straight: wait-die and wound-wait prevent deadlock using timestamps before it can happen; the wait-for graph detects it after it has happened; and detection must be paired with a victim-selection and rollback policy to be complete.

Scope — practical limits of detection. Detection is attractive when deadlocks are rare (short transactions, light contention); prevention is preferred when they are likely (long transactions, heavy contention) (T1 §22.1.6). Victim selection must avoid repeatedly sacrificing the same transaction — a fairness failure called starvation; engines usually give previously aborted transactions higher priority. A cheaper fallback used in practice is the timeout: if a transaction waits longer than a threshold, assume deadlock and abort it — simple and low-overhead, at the cost of aborting transactions that were merely slow, not deadlocked (T1 §22.1.6; T2 §17.4).

Exam note — the contrast to keep straight:

Scheme	Strategy	Mechanism	When it acts
Wait-die / wound-wait	Prevent	Timestamp-based rules make circular wait impossible	Before deadlock forms
Wait-for graph	Detect	Cycle search on the wait graph, then victim abort	After deadlock forms
Timeout	Detect (heuristic)	Abort any transaction waiting too long	After an arbitrary wait

Real-world: commercial databases default to detection — MySQL InnoDB and PostgreSQL both detect deadlocks by wait-for graph analysis and abort one of the transactions, returning the familiar "deadlock detected, transaction rolled back" error; prevention schemes are more common in specialized and distributed systems where the cost of a detected-and-aborted transaction is unacceptable.

Where this matters in the field: the wait-for graph is literally the OS resource-allocation graph — same vertices-and-edges construction, same cycle-detection algorithm, different labels (processes and devices vs transactions and data items). Anyone who has seen the OS version has seen this one; the skill transfers directly to distributed systems and cloud computing, as the session notes.

16.8 Thomas' Write Rule: Timestamp-Ordering Optimization

The timestamp protocol of section 16.4 rolls back a transaction whenever it issues an outdated operation. Thomas' write rule is the classic optimization that makes the protocol less wasteful, and it is the syllabus's named timestamp-ordering optimization.

Recall the basic write rule: when $T_{i}$ writes $Q$ , if $T S (T_{i}) < W (Q)$ , the write is rejected and $T_{i}$ rolls back — a younger transaction has already written $Q$ , so the value $T_{i}$ is about to write would be immediately overwritten. Thomas' write rule: in that case, ignore the obsolete write instead of aborting the transaction. The transaction continues executing as if the write had succeeded; the write itself is simply dropped.

16.8.1 The Rule: Ignore the Obsolete Write

The rule, formalized (reconciled with T1 §22.2.2 and T2 §17.6.2, which state the identical three-case test):

$On write of Q by T_{i} : if T S (T_{i}) < R (Q) : reject the write; roll back T_{i} (read check unchanged) else if T S (T_{i}) < W (Q) : ignore the write; T_{i} continues (write check relaxed) otherwise: execute the write; W (Q) \leftarrow T S (T_{i})$

The read rule of the basic protocol is untouched — only the obsolete-write branch changes from "roll back" to "skip the write and continue."

16.8.2 Why Ignoring Is Safe: The Timing Argument

Why this is safe requires the timing argument. If $T S (T_{i}) < W (Q)$ , some younger transaction $T_{j}$ (with $T S (T_{j}) = W (Q) > T S (T_{i})$ ) has already written $Q$ . Any transaction that reads $Q$ after this point and has a timestamp larger than $T S (T_{j})$ will read $T_{j}$ 's value, not $T_{i}$ 's; any transaction with a timestamp smaller than $T S (T_{i})$ that has not yet read $Q$ could still read $Q$ — but a transaction $T_{k}$ with $T S (T_{k}) < T S (T_{i})$ reading $Q$ would check $T S (T_{k}) < W (Q)$ and would itself be rolled back under the basic rules. The value $T_{i}$ wanted to write can therefore never be read by anyone — the write is dead on arrival, and rolling back the whole transaction to undo a write nobody could ever see is pure waste. The rule's one remaining condition: if $T S (T_{i}) < R (Q)$ — a younger transaction has already read $Q$ , and the value it read would have been $T_{i}$ 's — the transaction still rolls back, exactly as in the basic protocol, because that read genuinely depended on $T_{i}$ 's write.

Worked example — the section 16.4.8 schedule under Thomas' rule. $T_{1}$ (ts 1) writes $Q$ ; $T_{2}$ (ts 2) writes $Q$ (allowed, $W (Q) = 2$ ); then $T_{1}$ writes $Q$ again.

Step	Operation	Check	Basic protocol	Thomas' rule
1	$T_{1}$ writes $Q$	fresh item	allowed; $W (Q) = 1$	allowed; $W (Q) = 1$
2	$T_{2}$ writes $Q$	$2 < R (Q) = 0$ ? No. $2 < W (Q) = 1$ ? No	allowed; $W (Q) = 2$	allowed; $W (Q) = 2$
3	$T_{1}$ writes $Q$ again	$1 < R (Q)$ ? No. $1 < W (Q) = 2$ ? Yes	$T_{1}$ rolls back	write ignored; $T_{1}$ continues

Final answer: under Thomas' rule, $T_{1}$ finishes its work instead of rolling back — the dropped write of $Q$ was going to be overwritten by $T_{2}$ 's newer value anyway. Sense-check: nobody can ever observe $T_{1}$ 's second write of $Q$ (any reader with a timestamp above 2 sees $T_{2}$ 's value; any reader below 1 is itself rolled back), so dropping it changes nothing observable.

16.8.3 The One Honest Cost: View Serializability

The one honest cost of the optimization: a schedule accepted under Thomas' rule can fail the conflict serializability test even though it is view serializable — the ignored write-write conflict is precisely the kind of operation the conflict graph would have flagged, and view serializability is the weaker property that still guarantees correctness. That fact is the exam point: Thomas' write rule trades conflict serializability (which the basic protocol guarantees) for fewer aborts, keeping the weaker but still correct view serializability.

Scope — what the rule does and does not preserve. The reference treatment is explicit (T2 §17.6.2): without the rule, the timestamp protocol allows only conflict serializable schedules; with the rule, some schedules are permitted that are not conflict serializable — but those schedules are view serializable, equivalent to the serial schedule obtained by deleting the never-seen obsolete write (T2 Figure 17.7 shows the deletion explicitly). Recoverability is another matter: like the basic protocol, Thomas' rule alone does not guarantee recoverable schedules, and the buffering/strict-TO modification is still required in practice.

Exam note — the contrast to memorize. Basic timestamp ordering: outdated write → abort the whole transaction (conflict serializability preserved). Thomas' write rule: outdated write → ignore the write, keep the transaction (fewer aborts, view serializability preserved). The read check ( $T S (T_{i}) < R (Q)$ ) never changes — a junior that already read the item depends on $T_{i}$ 's value, and that dependency cannot be ignored away. Recognize both the cost (weaker guarantee) and the benefit (no needless rollbacks) on a question.

Where this matters in the field: the obsolete-write insight is why modern versioned engines do not panic over a late write — a transaction writing a version that is already superseded simply has its write discarded (or its version garbage-collected), rather than aborting users. The "ignored write is dead on arrival" argument is the same reasoning MVCC uses to keep old versions readable without blocking writers.

16.9 Lock Conversion and the 2PL Spectrum

16.9.1 Lock Conversion: Upgrading and Downgrading

A transaction often does not know in advance whether it will only read an item or also write it — it reads $A$ first, then decides it must update $A$ . The mechanism for this is lock conversion. A transaction holding a shared lock may upgrade it to an exclusive lock (read-then-write on the same item), and a transaction holding an exclusive lock may downgrade it to a shared lock (write, then only read afterwards). Two constraints govern conversions in the 2PL world:

Upgrade is a lock acquisition in disguise: an exclusive lock is a stronger lock, and it is granted only when no other transaction holds a shared lock on the item — otherwise upgrading would create an uncommitted-writer exposure. Upgrading therefore belongs to the growing phase (it can only happen while the transaction is still acquiring locks).
Downgrade releases part of the lock's strength, so it belongs to the shrinking phase — and once a transaction has downgraded (or released) any lock, it has entered the shrinking phase and may acquire nothing further.

Why upgrade needs the "sole holder" condition — the machinery. The shared/exclusive scheme counts concurrent readers on a read-locked item (T1 §22.1.1). If $T$ alone holds the shared lock, its upgrade to exclusive is simply a mode change. If other transactions also hold shared locks, the exclusive lock cannot be granted to any of them — each upgrade request must wait until the other readers release. The lock manager's reader-count field exists precisely to make this decision. In the R1 (§18.1.3) notation, the operations are written $S (Q) \to X (Q)$ for upgrade and $X (Q) \to S (Q)$ for downgrade.

Worked example — the upgrade deadlock (a classic production failure). Two transactions both read $A$ , then both decide to update it.

Step	$T_{1}$	$T_{2}$	Lock on $A$
1	lock-S(A) — granted		S by $T_{1}$ (readers: 1)
2		lock-S(A) — granted	S by $T_{1}$ , $T_{2}$ (readers: 2)
3	read(A)	read(A)
4	upgrade: lock-X(A) — denied, waits		$T_{2}$ still holds S
5		upgrade: lock-X(A) — denied, waits	$T_{1}$ still holds S

Final answer: each transaction waits for the other's shared lock to be released — a two-node wait cycle $T_{1} \to T_{2} \to T_{1}$ , i.e. deadlock on the upgrade. Sense-check: neither transaction can release its shared lock (that would mean abandoning its own upgrade), so the wait-for graph has a cycle and the system must abort one victim. The asymmetry matters in practice: two transactions that both read an item and then both want to update it can deadlock on the upgrade — each holds a shared lock and each waits for the other to release, so an exclusive upgrade can be granted to neither. Upgrade deadlocks are a classic production failure, and they are exactly the circular-wait situation the wait-for graph of 16.7 would catch.

16.9.2 Basic, Strict, and Rigorous 2PL: The Full Spectrum

Section 16.3 presented strict and rigorous 2PL against the baseline of "simple" 2PL; the syllabus asks for all three named explicitly, so the complete spectrum in one place:

Basic 2PL. Growing phase: acquire any locks. Shrinking phase (after the first release): release only. The guarantee: conflict serializability — no schedule a basic-2PL run can produce fails the conflict test. The gap: a transaction may release an exclusive lock before commit, so another transaction can read its uncommitted value — basic 2PL does not guarantee recoverability or cascadelessness, and dirty reads are possible.
Strict 2PL. Same two phases, plus: exclusive locks are held until commit (or abort). Shared locks may still be released during the shrinking phase. The guarantee: conflict serializability and recoverability — no transaction can read an uncommitted value that later disappears, because the writer's exclusive locks are still held when readers arrive; cascading rollback becomes impossible.
Rigorous 2PL. All locks — shared and exclusive — are held until commit. There is no shrinking phase at all; the transaction acquires, commits, and releases everything at once. The guarantees: conflict serializability, recoverability, cascadelessness — and the strictest schedules of all, since nothing a transaction reads can have been written by an uncommitted transaction.

Protocol	Releases shared locks before commit	Releases exclusive locks before commit	Conflict serializable	Recoverable / cascadeless
Basic 2PL	yes (shrinking phase)	yes	yes	no
Strict 2PL	yes	no (held to commit)	yes	yes
Rigorous 2PL	no	no	yes	yes

The progression is a pure cost-benefit ladder, the same shape as the BCNF-versus-3NF discussion: each stricter variant buys an additional safety property by holding locks longer, which lengthens waits and reduces concurrency. Nothing is free — and the "conservative 2PL" variant previewed in the previous session (acquire all locks before the transaction starts, eliminating waits entirely) is the final rung in the same trade: deadlock-free by preclaiming, at the cost of the lowest concurrency of all.

Scope — where the spectrum sits among all the protocols. Basic 2PL is the serializability floor: any correct engine must be at least this. Strict 2PL is the practical default in commercial engines (write locks to commit, read locks released early where the isolation level allows). Rigorous 2PL approximates the strongest common isolation level (SERIALIZABLE). Conservative 2PL is the textbook extreme — preclaim all locks or none, deadlock-free and wait-free at the price of knowing all needed items in advance, which is rarely practical (T2 §17.4.1). The 2PL family, the timestamp family (16.4), and the deadlock machinery (16.6–16.7) together form the complete concurrency-control landscape this session covers.

Recap + bridge. Lock conversion (upgrade in the growing phase, downgrade in the shrinking phase) makes 2PL practical for read-then-write workloads while keeping the serializability guarantee — and introduces the upgrade deadlock, caught by the wait-for graph. The basic–strict–rigorous ladder organizes every variant by one question: what may be released before commit? The answer — shared only, exclusive only, or nothing — determines exactly which safety properties the schedule inherits.

Where this matters in the field: engines expose this spectrum through isolation levels — READ COMMITTED is a strict-2PL-like release discipline on read locks, REPEATABLE READ holds shared locks longer, SERIALIZABLE approximates rigorous 2PL. The next time a production deadlock report shows two SELECT ... FOR UPDATE statements upgrading rows, you are looking at section 16.9.1's upgrade deadlock in the wild.

Exam Guidance Summary

Concurrency anomalies (syllabus supplement, 16.5). Be ready to name and construct the three anomalies — dirty read (reading an uncommitted value that later rolls back), unrepeatable read (same item, two different committed values), incorrect summary (an aggregate over a mixture of pre- and post-update values), and phantom read (a new tuple appearing inside a range query). For each, say which isolation property fails and which protocol rule closes the gap. The R2-style conflict taxonomy helps: RW conflicts enable inconsistent analysis and nonrepeatable reads, WR conflicts enable dirty reads, WW conflicts enable lost updates — and RR conflicts never cause problems.
Deadlock material (syllabus supplement, 16.6–16.7). Wait-die vs wound-wait: memorize the two-by-two table (older waits in wait-die, older wounds in wound-wait) and the monotone-argument for why both prevent deadlock. The wait-for graph: node per transaction, edge $T_{i} \to T_{j}$ when $T_{i}$ waits on $T_{j}$ , cycle $⟺$ deadlock, recovery by victim selection and abort.
Thomas' write rule (syllabus supplement, 16.8). An outdated write ( $T S (T_{i}) < W (Q)$ ) is ignored rather than aborted — provided $T S (T_{i}) \neq < R (Q)$ . Know why it is safe (the write could never be read) and its cost (schedules may be view serializable but not conflict serializable).
Lock conversion (syllabus supplement, 16.9). Upgrade (shared → exclusive) belongs to the growing phase and can deadlock between two readers; downgrade (exclusive → shared) belongs to the shrinking phase. The three-protocol spectrum: basic (conflict serializable only), strict (exclusive locks to commit: + recoverable/cascadeless), rigorous (all locks to commit).
Assume and state your assumptions. When a problem's operations are ambiguous — the recurring example is whether a display statement counts as a read — write the assumption explicitly in your answer ("assuming that displaying involves reading") and carry it through consistently. This is the settled rule: if there is some ambiguity about whether an operation involves reading, you need to write the assumption, then apply the rules consistently under it.
Use the timestamps the question gives. For a timestamp-protocol problem, read the transaction timestamps directly from the question; the timestamps of the data items are the timestamps of the transactions that last read/wrote them, not wall-clock times.
The two check rules are exam ammunition. For a read: check only the item's write timestamp — if the transaction's timestamp is less, reject and roll back. For a write: check both the read timestamp and the write timestamp — reject on either being larger. Rollback means the whole transaction restarts with a new, later timestamp.
Expected problem types. Applying locks and releases across transaction schedules and checking what may or may not happen; classifying a schedule under simple, strict, and rigorous 2PL; walking a timestamp-protocol schedule instruction by instruction with all intermediate timestamp updates.
Know the protocol landscape. The three 2PL variants and why each exists (ACID, recoverability, cascading rollback freedom, deadlock freedom); what locks alone fail to guarantee; the timestamp protocol's read and write rules; what it guarantees (conflict serializability, no deadlock) and what it still risks (the recoverability question — answered by strict timestamp ordering).
Self-study (explicitly not in this course): deadlock detection and recovery — wait-die, wound-wait, the wait-for graph; these appear in other courses (operating systems, distributed systems) and the course deliberately does not examine them.
How to study. Re-read the recorded sessions for the primary coverage and treat the live material as the complementary view; then practice on different transactions and schedules — one or two solved problems at minimum, because an exam question without prior practice will make you stumble.
Breadth of the topic. The concurrency-control story spans three or four sessions of the course; the lock/timestamp material is core, not a side topic.

Key Industry Applications

Real-world: every modern booking and payment flow runs on concurrent transactions — railway reservation (IRCTC), flight reservation, hotel booking, e-commerce purchases, digital wallet (UPI) payments — and every one of them needs the ACID guarantees under concurrency that these protocols protect.
Real-world: the token number system used by Domino's-style chains, hospitals, pilgrimages, and banks is the everyday version of the timestamp protocol — assign a number at entry, and the order of service becomes explicit and fair.
Real-world: the wait-for graph is the resource allocation graph from operating systems, appearing identically in distributed systems and cloud computing — same algorithms, different labels (process vs transaction, resource vs conflicting operation).
Real-world: commercial engines implement the theory directly — MySQL InnoDB and PostgreSQL detect deadlocks by wait-for graph analysis and abort a victim ("deadlock detected, transaction rolled back"); InnoDB's next-key locking is the gap-lock solution to the phantom problem; and the SQL isolation levels (READ UNCOMMITTED to SERIALIZABLE) are exactly the anomaly-prevention ladder of section 16.5.
Real-world: SQL itself exposes the indexing machinery from the indexing chapter — creating B+ tree and other index types, choosing where they are stored — so the index-design decisions studied in the course are directly usable in a production database.

DDA Lecture 16 notes · Concurrency Control: Lock-Based and Timestamp-Based Protocols

Database Design and Applications· postgraduate· 2026-08-06

Sections Breakdown

116.1 Why Concurrency Control at All

Why serial access loses users and idles the processor; the ACID contract and the serializability yardstick every protocol must satisfy.

216.2 Lock-Based Protocols

Shared and exclusive locks, the compatibility matrix, the schedule that slips past plain locking, and deadlock under plain locking.

316.3 Two-Phase Locking (2PL)

Growing and shrinking phases, the lock point, strict and rigorous 2PL, the lock manager, and the wait-die, wound-wait, and wait-for-graph strategies.

416.4 The Timestamp-Based Protocol

Transaction and data-item timestamps, the read and write rules with full worked walkthroughs, and what the protocol guarantees.

516.5 Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom

The three anomalies, their conflict signatures, and how strict locking and isolation levels close them.

616.6 Deadlock Prevention: Wait-Die and Wound-Wait

The two age-based prevention schemes, why their wait edges are acyclic, and the starvation trade-off.

716.7 Deadlock Detection and Recovery: The Wait-For Graph

Building the wait-for graph, cycle detection, victim selection and abort, and the timeout heuristic.

816.8 Thomas' Write Rule: Timestamp-Ordering Optimization

Ignoring obsolete writes safely, the timing argument, and the one honest cost: view serializability.

916.9 Lock Conversion and the 2PL Spectrum

Upgrading and downgrading locks, the simultaneous-upgrade deadlock trap, and the basic-strict-rigorous spectrum.

10Exam Guidance Summary

The professor's exam strategy: the timestamp check rules, assumptions to state, and how to classify schedules.

11Key Industry Applications

How the theory maps to production engines: InnoDB and PostgreSQL deadlock detection, next-key locking, and isolation levels.

Postgraduate students in Database Design and Applications

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Why Concurrency Control at All

Must-know: Concurrency buys response time and processor utilization; serial access is correct but loses users and idles the processor. The engine must keep ACID (atomicity, consistency, isolation, durability) while interleaving transactions, and it does so by permitting only conflict serializable schedules.

⚠️ Top pitfall: Confusing the contract (ACID) with the mechanism (locking/timestamps): locking only orders access; atomicity, isolation, and durability are enforced by other subsystems.

Self-check: Why is the processor idle under serial execution even though it is doing the same total work?

Connects to: Lock-Based Protocols, Two-Phase Locking (2PL)

Lock-Based Protocols

Must-know: Plain shared/exclusive locking is locally correct but globally unsafe: the grant decision looks only at one item, never at the whole schedule. Two failure modes: non-conflict-serializable schedules (T1->T2 and T2->T1 cycle on B and A) and deadlock (circular wait). The fix is a lock discipline (2PL).

⚠️ Top pitfall: Believing a lock grant implies schedule safety — the local rule does not imply the global property; also, concurrent transactions see the main-memory image, not the durable disk value.

Self-check: In the two-account example, why does plain locking allow the display of 250 instead of 300?

Connects to: Why Concurrency Control at All, Two-Phase Locking (2PL), Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom

Two-Phase Locking (2PL)

Must-know: 2PL: after the first release you may never acquire again — this makes schedules conflict serializable by ordering transactions by lock point. Strict 2PL holds exclusive locks to commit (recoverable, cascadeless); rigorous 2PL holds all locks to commit. Acquisitions may be interspersed with reads/writes; only releases are restricted.

⚠️ Top pitfall: Thinking the two phases restrict reads vs writes — they restrict acquisitions vs releases; also confusing the professor's in-scope protocol material with the self-study deadlock-handling material.

Self-check: Why does holding exclusive locks until commit prevent cascading rollbacks?

Connects to: Lock-Based Protocols, The Timestamp-Based Protocol, Deadlock Prevention: Wait-Die and Wound-Wait, Deadlock Detection and Recovery: The Wait-For Graph, Lock Conversion and the 2PL Spectrum

The Timestamp-Based Protocol

Must-know: Timestamp protocol: for a read check only the item's write timestamp; for a write check both read and write timestamps. Reject (roll back, reborn with a fresh later timestamp) when the transaction's timestamp is smaller. The serialization order is exactly timestamp order; no transaction ever waits, so deadlock is impossible. Basic TO does not guarantee recoverability — strict TO (buffer/delay until the writer commits) fixes it.

$read Q by T_{i} : if T S (T_{i}) < W (Q) reject/roll back; else R (Q) \leftarrow max (R (Q), T S (T_{i})) . write Q by T_{i} : if T S (T_{i}) < R (Q) or T S (T_{i}) < W (Q) reject/roll back; else W (Q) \leftarrow T S (T_{i}) .$

⚠️ Top pitfall: Recording wall-clock access times instead of transaction timestamps on data items; forgetting the display-read assumption; assuming the write timestamp becomes the speaker's slip value 'four' instead of the writer's own timestamp 5.

Self-check: In the walkthrough, why is T1's write of A at time 16 rejected (TS(T1)=3, R(A)=12)?

Connects to: Two-Phase Locking (2PL), Thomas' Write Rule: Timestamp-Ordering Optimization

Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom

Must-know: Dirty read = reading an uncommitted value that later rolls back (WR conflict; fixed by recoverability/strict 2PL). Unrepeatable read = same item, two different committed values (RW conflict). Incorrect summary = aggregate mixing pre- and post-update values (40+50+20=110 vs true 120). Phantom = new row inside a range query, undefeatable by row locks — needs gap/next-key locking or SERIALIZABLE.

⚠️ Top pitfall: Claiming row locking stops phantoms — it cannot, because the phantom row did not exist to be locked; the lock must cover the index gap.

Self-check: Which isolation level eliminates the dirty read but still permits the unrepeatable read?

Connects to: Lock-Based Protocols, Two-Phase Locking (2PL)

Deadlock Prevention: Wait-Die and Wound-Wait

Must-know: Two-by-two table: older requests lock held by younger -> wait-die: older waits; wound-wait: older wounds (aborts) the younger. Younger requests lock held by older -> wait-die: younger dies (restarts, same timestamp); wound-wait: younger waits. Deadlock-free because wait edges are strictly monotone in age. Restarts keep the original timestamp so the transaction eventually becomes oldest.

⚠️ Top pitfall: Confusing the two schemes' directions, and confusing restart-with-same-timestamp (wait-die/wound-wait) with the timestamp protocol's restart-with-new-timestamp.

Self-check: Under wound-wait, what happens when an older transaction requests a lock held by a younger one?

Connects to: The Timestamp-Based Protocol, Deadlock Detection and Recovery: The Wait-For Graph

Deadlock Detection and Recovery: The Wait-For Graph

Must-know: Wait-for graph: node per transaction, edge Ti->Tj when Ti waits for Tj, cycle <=> deadlock. Detection by periodic cycle search (DFS); recovery by victim selection (fewest locks / least work) and abort, releasing locks. Contrast with prevention: wait-die/wound-wait act before, detection acts after, timeout is a low-overhead heuristic.

⚠️ Top pitfall: Treating a wait edge as a precedence edge — the graph records blocked transactions, and its cycle is the live deadlock signature.

Self-check: Why does aborting one transaction in a wait-for cycle unfreeze all the others?

Connects to: Lock-Based Protocols, Deadlock Prevention: Wait-Die and Wound-Wait

Thomas' Write Rule: Timestamp-Ordering Optimization

Must-know: Thomas' write rule: outdated write (TS(Ti) < W(Q)) is ignored, not aborted — provided TS(Ti) >= R(Q) (no junior has read the item). Safe because the write could never be read by anyone. Cost: schedules may be view serializable but not conflict serializable.

$if T S (T_{i}) < R (Q) : roll back; else if T S (T_{i}) < W (Q) : ignore the write; else: execute and set W (Q) \leftarrow T S (T_{i}) .$

⚠️ Top pitfall: Applying the rule when a junior has already read the item (TS(Ti) < R(Q)) — that read depends on the value and still forces a rollback.

Self-check: In the T1(1)/T2(2) Q schedule, why can T1's second write be ignored safely?

Connects to: The Timestamp-Based Protocol

Lock Conversion and the 2PL Spectrum

Must-know: Upgrade (S->X) belongs to the growing phase and is granted only when no other transaction holds a shared lock — two readers upgrading simultaneously deadlock. Downgrade (X->S) belongs to the shrinking phase. Spectrum: basic 2PL (conflict serializable only), strict (exclusive locks to commit: + recoverable/cascadeless), rigorous (all locks to commit); conservative 2PL preclaims everything.

⚠️ Top pitfall: Upgrading without checking other shared holders; forgetting that a downgrade enters the shrinking phase and forbids further acquisitions.

Self-check: Why can two transactions that both read A and both want to update A deadlock?

Connects to: Two-Phase Locking (2PL), Deadlock Detection and Recovery: The Wait-For Graph

Exam Guidance Summary

Must-know: For a read check only the item's write timestamp; for a write check both timestamps; rollback restarts with a new later timestamp. Write down ambiguous assumptions (e.g., display = read). Use the timestamps the question gives. Classify schedules under basic/strict/rigorous 2PL and walk timestamp schedules step by step.

$read: if T S (T_{i}) < W (Q) reject; else R (Q) \leftarrow max (R (Q), T S (T_{i})) . write: if T S (T_{i}) < R (Q) or T S (T_{i}) < W (Q) reject; else W (Q) \leftarrow T S (T_{i}) .$

⚠️ Top pitfall: Not stating the display-read assumption; using wall-clock times instead of transaction timestamps on data items.

Self-check: What are the two check rules for the timestamp protocol?

Connects to: The Timestamp-Based Protocol, Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom, Deadlock Prevention: Wait-Die and Wound-Wait, Thomas' Write Rule: Timestamp-Ordering Optimization

Key Industry Applications

Must-know: The theory maps directly to production: InnoDB/PostgreSQL detect deadlocks with the wait-for graph, next-key locking prevents phantoms, and SQL isolation levels are the anomaly ladder.

⚠️ Top pitfall:

Self-check: Which real-world systems implement the wait-for graph?

Connects to: Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom, Deadlock Detection and Recovery: The Wait-For Graph

Previous LectureLecture 15 · Transactions: Schedules, Serializability, and Recovery

Next LectureLecture 17 · Database Recovery, Checkpointing, and the NoSQL Shift

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

16.1 Why Concurrency Control at All

16.1.1 The Scope of This Session

16.1.2 The Motivation: Everyone Booking at Once

16.1.3 The Contract That Must Hold: Transactions and ACID

16.1.4 From Theory to Implementation: Serializability Recap

16.2 Lock-Based Protocols

16.2.1 Shared Locks and Exclusive Locks

16.2.2 The Problem: Locks Alone Do Not Guarantee Conflict Serializability

16.2.3 Student Question: Does Locking Not Already Protect ACID?

16.2.4 Student Question: Foreign Keys, Granularity, and Cascade Deletes

16.2.5 Student Question: Main Memory vs Disk — What Does the Other Transaction Actually See?

16.2.6 Deadlock Under Plain Locking

16.2.7 The Problem-First Teaching Method

16.3 Two-Phase Locking (2PL)

16.3.1 Growing Phase, Shrinking Phase, and the Lock Point

16.3.2 Strict Two-Phase Locking

16.3.3 Rigorous Two-Phase Locking

16.3.4 Student Question: May Read/Write Operations Sit Between Lock Statements?

16.3.5 Why the Variants Exist: Recoverability, Cascading Rollback, Deadlock Freedom

16.3.6 The Lock Manager and Lock Table

16.3.7 Deadlock Handling: Wait-Die, Wound-Wait, Wait-For Graphs

16.3.8 Student Question: Locking Happens in Main Memory

16.4 The Timestamp-Based Protocol

16.4.1 The Token Number Analogy

16.4.2 Transaction Timestamps and Data Item Timestamps

16.4.3 The Read Rule

16.4.4 The Write Rule

16.4.5 Worked Example: The Complete Read-Write Walkthrough

16.4.6 The Rules in Plain Language: Seniority, Not Write-Before-Read

16.4.7 Worked Example: Display, Read Timestamps, and the Ambiguity of "Reading"

16.4.8 Worked Example: A Later Write Beats an Earlier Write

16.4.9 Worked Example: Five Transactions, Timestamps 1 to 5

16.4.10 The Analogy That Clicks: Tokens, Birth Times, and Immutable Seniority

16.4.11 What the Timestamp Protocol Guarantees — and the Open Question

16.4.12 How Much of the Course This Is

16.5 Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom

16.5.1 The Dirty Read (Temporary Update) Problem

16.5.2 The Incorrect Summary and Unrepeatable Read Problems

16.5.3 The Phantom Read Problem

16.6 Deadlock Prevention: Wait-Die and Wound-Wait

16.6.1 The Wait-Die Scheme (Non-Preemptive)

16.6.2 The Wound-Wait Scheme (Preemptive)

16.6.3 Why Both Schemes Are Deadlock-Free

16.6.4 The Trade-Offs and Starvation

16.7 Deadlock Detection and Recovery: The Wait-For Graph

16.7.1 Building the Wait-For Graph

16.7.2 Detection: Finding Cycles

16.7.3 Recovery: Victim Selection and Abort

16.8 Thomas' Write Rule: Timestamp-Ordering Optimization

16.8.1 The Rule: Ignore the Obsolete Write

16.8.2 Why Ignoring Is Safe: The Timing Argument

16.8.3 The One Honest Cost: View Serializability

16.9 Lock Conversion and the 2PL Spectrum

16.9.1 Lock Conversion: Upgrading and Downgrading

16.9.2 Basic, Strict, and Rigorous 2PL: The Full Spectrum

Exam Guidance Summary

Key Industry Applications

DDA Lecture 16 notes · Concurrency Control: Lock-Based and Timestamp-Based Protocols

Sections Breakdown

Exam Revision Notes

Why Concurrency Control at All

Lock-Based Protocols

Two-Phase Locking (2PL)

The Timestamp-Based Protocol

Concurrency Anomalies: Dirty Read, Unrepeatable Read, Phantom

Deadlock Prevention: Wait-Die and Wound-Wait

Deadlock Detection and Recovery: The Wait-For Graph

Thomas' Write Rule: Timestamp-Ordering Optimization

Lock Conversion and the 2PL Spectrum

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat