GATE CS 2017 Set 1 Q42 — Transactions and Concurrency Control

The given algorithm is the standard Wound-Wait scheme used for deadlock prevention in database systems.

1. Deadlock-Freedom

Let us analyze when a transaction is allowed to wait:

• $T_2$ (the requesting transaction) is allowed to wait for $T_1$ (the holding transaction) only if $TS(T_2) > TS(T_1)$.
• This means a transaction can only wait for another transaction that is older than itself (i.e., has a smaller timestamp).

Since the wait-for relation only goes from a younger transaction to an older transaction ($T_{\text{young}} \to T_{\text{old}}$), a cycle in the wait-for graph is impossible because timestamps are unique and strictly ordered. Without a cycle, a deadlock cannot occur.

2. Starvation-Freedom

Let us analyze if a transaction can be rolled back indefinitely:

• When a transaction is killed, it is restarted with its original timestamp.
• As time progresses, the restarted transaction becomes older relative to newly entering transactions.
• Eventually, it becomes the oldest active transaction in the system.
• Once it is the oldest transaction, no other transaction can have a smaller timestamp. Thus, it will never be killed by any other transaction requesting a resource. Instead, it will either immediately acquire the resource (by killing the younger holder) or wait for it without being preempted.

Since every transaction eventually becomes the oldest and completes, the system is starvation-free.

Thus, the database system is both deadlock-free and starvation-free.