In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let TS(T_1) and TS(T_2) be the timestamps of transactions T_1 and T_2 respectively. Besides, T_1 holds a lock on the resource R and T_2 has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlock in the database system: if TS(T_1) < TS(T_2) then T_1 is killed else T_2 waits Assume any transaction that is killed terminates and is restarted with the same timestamp. Which of the following is TRUE about the database system? A. The database system is both deadlock-free and starvation-free. B. The database system is deadlock-free, but not starvation-free. C. The database system is starvation-free, but not deadlock-free. D. The database system is neither deadlock-free nor starvation-free.

GATE 2017 · Databases · Transaction and Concurrency · medium

Answer: B. The database system is deadlock-free (no circular wait can form since the holder is never waiting), but NOT starvation-free (the oldest transaction can be repeatedly killed by any younger transaction requesting its lock).

1. Compare with Wait-Die and Wound-Wait: Standard protocols: - Wait-Die: Older requester waits; younger requester dies (aborts). - Wound-Wait: Older requester wounds (kills) holder; younger requester waits. This algorithm (T1=holder, T2=requester): - If TS(T1) < TS(T2): T1 is older holder, T2 is younger requester -> T1 is KILLED. - Else (TS(T1) >= TS(T2)): T1 is younger or same age holder, T2 is older requester -> T2 WAITS. This is NOT standard Wait-Die or Wound-Wait. It is an unusual variant where the OLDER holder is killed when a younger transaction requests its lock.
2. Check for deadlock: In the algorithm: when T2 requests a lock held by T1: - Either T1 is killed (T1 no longer holds the lock, T2 can proceed) - Or T2 waits (T2 is not in a 'holds lock' state) For deadlock we'd need a cycle. But at any conflict: - The older transaction (holder with smaller TS) is killed - it dies, not waits - The younger transaction (requester with larger TS) either waits or gets the lock Since the holder never waits (it either dies or the requester waits), no cycle can form. Deadlock is IMPOSSIBLE - the algorithm is deadlock-free.
3. Check for starvation: Consider an older transaction T1 with small TS (say TS=1) that holds lock R. A newer T2 (TS=5) requests the lock: TS(T1)=1 < TS(T2)=5, so T1 is KILLED. T1 restarts with TS=1 (same timestamp). Later T1 again holds some lock R'. Another new transaction T3 (TS=10) requests R': TS(T1)=1 < TS(T3)=10, T1 is KILLED again. Since T1 is the oldest transaction (smallest TS), it will ALWAYS be killed whenever any newer transaction conflicts with it. T1 is restarted with the same TS=1, so it stays the oldest. T1 can be killed infinitely many times - this is STARVATION. The algorithm is NOT starvation-free.