Lab 7: Timestamp-based concurrency control

Preliminaries
Exercise 1: commit bits; one version of each data item
Exercise 2: no commit bits; multiple versions of each data item
Optional extra practice: Locking and deadlock detection

Preliminaries

We will be analyzing schedules of transactions in a system that uses some form of timestamp-based concurrency control.

In each exercise, there are three transactions (T1, T2 and T3) and three data items (X, Y and Z).

You should assume that:

The read and write timestamps of all of the data items are initially 0.
The timestamps assigned to the transactions are:
- TS(T1) = 100
- TS(T2) = 200
- TS(T3) = 300
These timestamps are consistent with the fact that, in the schedules we’ll be analyzing below, T1 starts first, followed by T2, followed by T3.

In giving your answers, you should fill in a table that begins as follows:

request	response	state changes and/or explanation
r1(Y)	allowed	RTS(Y) = 100

The third column should include any changes to the state maintained for the data item. If a request is denied or ignored, that column should also include a brief explanation of why.

You do not need to restart a transaction that is rolled back, which means that you can skip any requests by a transaction that come after the point at which it is rolled back.

Exercise 1: commit bits; one version of each data item

In this exercise, we will assume that the DBMS is using timestamp-based concurrency control with commit bits and with only one version of each data item.

What is the purpose of maintaining commit bits?

To prevent dirty reads, and to thereby produce schedules that are recoverable and cascadeless.

Consider the following schedule:

s1; r1(Y); s2; w2(Y); w2(X); s3; r3(Z); r2(Z); w3(Y); r3(X); c2; c3; w1(Y); r1(X); c1

How would the system respond to each of the requested actions?

In addition to the assumptions mentioned in the preliminaries, you should assume that all of the commit bits are initially true.
Make sure to include the responses to the commit requests (c1, c2, c3), since they are relevant when a system uses commit bits.
If a transaction is made to wait, you should include the relevant request a second time when the transaction is allowed to try again.

request	response	state changes and/or explanation
r1(Y)	allowed	RTS(Y) = 100
w2(Y)	allowed	WTS(Y) = 200, c(Y) = false
w2(X)	allowed	WTS(X) = 200, c(X) = false
r3(Z)	allowed	RTS(Z) = 300
r2(Z)	allowed	RTS is not changed (see below)
w3(Y)	allowed	WTS(Y) = 300, C(Y) remains false
r3(X)	denied; make wait	TS(T3) >= WTS(X) but c(X) == false
c2	allowed	c(X) = true
r3(X)	allowed!	RTS(X) = 300
c3	allowed	c(Y) = true
w1(Y)	ignored	TS(T1) >= RTS(Y) but TS(T1) < WTS(Y)
		and c(Y) == true
r1(X)	denied; roll back	TS(T1) < WTS(X); RTS(Y) = 0
c1	doesn’t happen	T1 has already been rolled back

Here are some additional notes about each request:

r1(Y):
- test: TS(T1) ≥ WTS(Y), 100 ≥ 0, true
- second test: c(Y) is true, so allow the read without a wait
- change: RTS(Y) = max(RTS(Y),TS(T1)) = max(0,100) = 100
- Note: If we weren’t using commit bits, we wouldn’t need the second test, and the read would be allowed as long as the first test is passed.
w2(Y):
- first test: TS(T2) ≥ RTS(Y), 200 ≥ 100, true
- second test: TS(T2) ≥ WTS(Y), 200 ≥ 0, true, so allow
- change: WTS(Y) = TS(T2) = 200
- we also set c(Y) to false to indicate that the writer of Y’s current value has not yet committed
w2(X):
- first test: TS(T2) ≥ RTS(X), 200 ≥ 0, true
- second test: TS(T2) ≥ WTS(X), 200 ≥ 0, true, so allow
- change: WTS(X) = TS(T2) = 200
- we also set c(X) to false to indicate that the writer of X’s current value has not yet committed
r3(Z):
- test: TS(T3) ≥ WTS(Z), 300 ≥ 0, true
- second test: c(Z) is true, so allow the read without a wait
- change: RTS(Z) = max(RTS(Z),TS(T3)) = max(0,300) = 300
r2(Z):
- test: TS(T2) ≥ WTS(Z), 200 ≥ 0, true
- second test: c(Z) is true, so allow the read without a wait
- change: RTS(Z) = max(RTS(Z),TS(T3)) = max(300,200) = 300
- Note that the RTS doesn’t change in this case! The RTS is not necessarily the timestamp of the most recent reader. Rather, it is the timestamp of the reader that comes latest in the equivalent serial schedule. These values may not be the same because reads don’t conflict with each other and thus they don’t need to follow the timestamp ordering.
w3(Y):
- first test: TS(T3) ≥ RTS(Y), 300 ≥ 100, true
- second test: TS(T3) ≥ WTS(Y), 300 ≥ 200, true, so allow
- change: WTS(Y) = TS(T3) = 300
- c(Y) remains true, and T3 becomes Y’s most recent writer.
- Note that the WTS is always the timestamp of the most recent writer, since writes are only allowed if they follow the timestamp ordering – i.e., if the transaction requesting the write comes later in the timestamp ordering than the writer of the previous value.
r3(X):
- test: TS(T3) ≥ WTS(X), 300 ≥ 200, true
- second test: c(X) is false, so make T3 wait, which prevents what would otherwise be a dirty read, because the writer of the prior value of X (T2) has not yet committed.
- If we weren’t using commit bits, this read would be allowed!
c2: T2 commits
- c(X) is set to true because T2 is the writer of X’s current value.
- Note that we do not set c(Y) to true. T2 did write Y, but T3 overwrote that value, so T2 is not the writer of Y’s current value.
- If we weren’t using commit bits, we could ignore the commits, since they aren’t relevant in the absence of commit bits
r3(X): now that c(X) is true, T3 is allowed to try again and the read is allowed.
c3: T3 commits.
- c(Y) is set to true because T3 is the writer of Y’s current value.
w1(Y):
- first test: TS(T1) ≥ RTS(Y), 100 ≥ 100, true
- second test: TS(T1) ≥ WTS(Y), 100 ≥ 300, false, so don’t allow
- third test: c(Y) is true, so ignore the write.
- Note that the write cannot be allowed, because the current value of Y was written by T3, which comes after T1 in the equivalent serial schedule based on the timestamps. The DBMS ignores the request—treating T1’s write as if it occurred before the write by T3 and was overwritten.
- Note: If c(Y) were false in this case, T1 would be made to wait, since the value that it wants to write may be needed if (1) the writer of Y’s current value is rolled back and (2) there is another transaction waiting to read Y when the rollback occurs.
- If we weren’t using commit bits, we wouldn’t need the third test to know that we should ignore the write.
r1(X):
- test: TS(T1) ≥ WTS(X), 100 ≥ 200, false, so deny and roll back
- Note that the WTS tells us that T2 wrote the current value of X. T1 comes before T2 in the equivalent serial schedule, so it should have read the original value of X instead of its current value. Thus, this read cannot be allowed. The system rolls back T1 and will later restart it with a larger timestamp.
- Since T1 is the latest reader of Y (RTS(Y) == 100), we restore RTS(Y) to its prior value of 0.
c1: T1 has already been rolled back, so this action doesn’t occur.

Exercise 2: no commit bits; multiple versions of each data item

In this exercise, we will assume that the DBMS is using timestamp-based concurrency control without commit bits and with multiple versions of each item.

What is the purpose of maintaining multiple versions?

To prevent rollbacks that stem from reading an item.

Consider the following schedule (which is slightly different than the one from Exercise 1):

s1; r1(Y); s2; w2(Y); w2(X); s3; r3(Z); r2(Z); w3(Y); r3(X); c2; c3; r1(X); w1(Z); c1

How would the system respond to each of the requested actions?

You should make the same assumptions as before about the timestamps of the transactions and the initial timestamps of the data items.
Make sure to create a new version of a data item whenever necessary.
Because commits don’t have an effect when we’re not using commit bits, you do not need to include the commit actions (c1, c2, etc.) in your table.

request	response	state changes and/or explanation
r1(Y)	allowed to read Y(0)	RTS(Y(0)) = 100
w2(Y)	allowed	create Y(200) with RTS = 0
w2(X)	allowed	create X(200) with RTS = 0
r3(Z)	allowed to read Z(0)	RTS(Z(0)) = 300
r2(Z)	allowed to read Z(0)	RTS(Z(0)) is unchanged
w3(Y)	allowed	create Y(300) with RTS = 0
r3(X)	allowed to read X(200)	RTS(X(200)) = 300
r1(X)	allowed to read X(0)	RTS(X(0)) = 100
w1(Z)	denied; rollback	RTS(X(0)) = 0; RTS(Y(0)) = 0

Here are some additional notes about each request:

r1(Y):
- test: none, because reads are always allowed when there are multiple versions!
- the DBMS finds the appropriate version for T1 to read based on its timestamp, which in this case is the original version, Y(0)
- change: RTS(Y(0)) = max(RTS(Y(0),TS(T1)) = max(0,100) = 100
w2(Y):
- start by finding the version of Y that T2 should be overwriting based on its timestamp, which in this case is Y(0)
- only test: TS(T2) ≥ RTS(Y(0)), 200 ≥ 100, true, so allow
- the write creates a new version of Y, Y(200) – i.e., a version of T whose WTS is 200. The RTS of the new version is initially 0.
- note that we don’t need to compare TS(T2) to WTS(Y), because writes are never ignored when there are multiple versions
w2(X):
- T2 should be overwriting X(0)
- only test: TS(T2) ≥ RTS(X(0)), 200 ≥ 0, true, so allow
- a new version X(200) is created with RTS = 0
r3(Z):
- the DBMS finds the appropriate version for T3 to read based on its timestamp, which in this case is the original version, Z(0)
- change: RTS(Z(0)) = max(RTS(Z(0),TS(T3)) = max(0,300) = 300
r2(Z):
- T2 should read Z(0)
- no state change, since T2 isn’t the reader of Z(0) that comes latest in the timestamp ordering.
w3(Y):
- there are two versions of Y: Y(0) and Y(200)
- based on its timestamp, T3 should be overwriting Y(200)
- only test: TS(T3) ≥ RTS(Y(200)), 300 ≥ 0, true, so allow
- a new version Y(300) is created with RTS = 0
r3(X):
- there are two versions of X: X(0) and X(200)
- based on its timestamp, T3 should be reading X(200)
- change: RTS(X(200)) = max(RTS(X(200),TS(T3)) = max(0,300) = 300
r1(X):
- there are two versions of X: X(0) and X(200)
- based on its timestamp, T1 should read X(0)
- change: RTS(X(0)) = max(RTS(X(0),TS(T1)) = max(0,100) = 100
w1(Z):
- there is only one version of Z: Z(0)
- only test: TS(T1) ≥ RTS(Z(0)), 100 ≥ 300, false, so deny and roll back.
- In the equivalent serial schedule based on the timestamps, T3 (and T2 as well!) should have read the version of Z that T1 wants to write, but they didn’t, so T1’s write is too late.
- We review all of the versions of the data items, and we see that RTS(X(0)) and RTS(Y(0)) both equal TS(T1). Therefore, as part of rolling back T1, we restore the previous RTS values of those versions.

Optional extra practice: Locking and deadlock detection

Assume that:

A DBMS is using rigorous two-phase locking.
An exclusive lock for an item is requested just before writing that item.
A shared lock for an item is requested (if needed) just before reading that item.
Upgrades of shared locks are allowed.
Update locks are not being used.
The system performs deadlock detection using a waits-for graph.
A transaction commits immediately after completing its final read or write.

Consider the following schedule involving the transactions T1, T2, and T3:

r1(X); r1(Z); w2(Y); w2(X); r3(Z); w3(Y); w1(Z)

Determine if this schedule would lead to deadlock.

If deadlock occurs, show the partial schedule in table form (including lock operations and any commits) up to the point of deadlock, along with the waits-for graph at the point of deadlock.

If deadlock does not occur, show the full schedule, including lock operations and commits. In that case, you do not need to include the waits-for graph.

In either case, your schedule should include any changes to the sequence of operations that occur because a transaction is forced to wait for a lock.

If two transactions wait for a lock held by the same other transaction, and that other transaction subsequently commits, you should assume that the waiting transaction with the smaller transaction number is granted its request first.
The schedule would lead to deadlock.

Here is the partial schedule in table form:

T1

T2

T3

sl(X); r(X)
sl(Z); r(Z)

xl(Z)
denied
wait for T3

xl(Y); w(Y)
xl(X)
denied
wait for T1

sl(Z); r(Z)
xl(Y)
denied
wait for T2

Here is the waits-for graph at the point of deadlock:

Explanation
1. r1(X): T1 requests and acquires a shared lock for X and reads X.
2. r1(Z): T1 requests and acquires a shared lock for Z and reads Z.
3. w2(Y): T2 requests and acquires an exclusive lock for Y and writes Y.
4. w2(X): T2 requests an exclusive lock for X, but T1 already holds a shared lock for X, so the request is denied and T2 is made to wait for T1. Add a directed edge from T2 to T1 in the waits-for graph.
5. r3(Z): T3 requests a shared lock for Z. T1 already holds a shared lock for Z, but multiple transactions are allowed to hold shared locks for the same data element, and thus T3 acquires the lock and reads Z.
6. w3(Y): T3 requests an exclusive lock for Y, but T2 already holds an exclusive lock for Y, so the request is denied and T3 is made to wait for T2. Add a directed edge from T3 to T2 in the waits-for graph.
7. w1(Z): T1 attempts to upgrade its shared lock for Z to an exclusive lock, but T3 also holds a shared lock for Z, and thus the request is denied and T1 is made to wait for T3. Adding a directed edge from T1 to T3 in the waits-for graph creates a cycle: T1 → T3 → T2 → T1.
The DBMS would detect the cycle in the waits-for graph and conclude that the three transactions are deadlocked. The DBMS would then abort and restart one of the transactions so that the others could make progress.

Depending on the transaction chosen to be aborted and restarted and when it is restarted, it’s possible that additional conflicts could occur, and even that deadlock could occur once again.

T1	T2	T3
sl(X); r(X) sl(Z); r(Z) xl(Z) denied wait for T3	xl(Y); w(Y) xl(X) denied wait for T1	sl(Z); r(Z) xl(Y) denied wait for T2

Now imagine that we change the final action in the schedule to w1(X):

r1(X); r1(Z); w2(Y); w2(X); r3(Z); w3(Y); w1(X)

How would that change your answer?

Deadlock would no longer occur.

Here is the full schedule in table form:

T1	T2	T3
sl(X); r(X) sl(Z); r(Z) xl(X); w(X) commit u(X); u(Z)	xl(Y); w(Y) xl(X) denied wait for T1 xl(X); w(X) commit u(X); u(Y)	sl(Z); r(Z) xl(Y) denied wait for T2 xl(Y); w(Y) commit u(Y); u(Z)

Explanation

Steps a-f are the same as before.

w1(X): T1 attempts to upgrade its shared lock for X to an exclusive lock. Since no one else has any locks for X, T1 is able to upgrade to an exclusive lock and write X.
T1 is now done, so it commits. And because the DBMS is using rigorous locking, T1 releases all of its locks at commit, which we show by putting the unlock actions after the commit action.
w2(X): Now that T1 has released its lock for X, T2 can try again to acquire an exclusive lock for X. Since no one has any locks on X, T2 can acquire the exclusive lock and write X.
T2 is now done, so it commits and releases its locks.
w3(Y): Now that T2 has released its lock for Y, T3 can try again to acquire an exclusive lock for Y. Since no one has any locks on Y, T3 can acquire the exclusive lock and write Y.
T3 is now done, so it commits and releases its locks.

Note that the need to wait for locks has modified the order of some of the actions. The final schedule is:

r1(X); r1(Z); w2(Y); r3(Z); w1(X); w2(X); w3(Y)

Last updated on November 3, 2025.