Timestamp-Based Protocols

Unlike lock-based protocols (where transactions acquire locks and potentially deadlock), Timestamp-Based Protocols assign a unique timestamp to each transaction when it enters the system. The system uses these timestamps to determine the serialization order, ensuring conflict serializability without any locks.

1. Timestamp Ordering Protocol

Each data item $Q$ maintains two timestamps:

• W-timestamp(Q): The timestamp of the last transaction that successfully wrote $Q$.
• R-timestamp(Q): The timestamp of the last transaction that successfully read $Q$.

When Transaction $T_i$ with timestamp $TS(T_i)$ issues an operation:

Read(Q):

• If TS(T_i) < W-timestamp(Q): $T_i$ is trying to read a value that was already overwritten by a younger transaction. Reject and rollback $T_i$.
• Otherwise: Allow the read. Update R-timestamp(Q) = max(R-timestamp(Q), TS(T_i)).

Write(Q):

• If TS(T_i) < R-timestamp(Q): $T_i$ is trying to overwrite a value that a younger transaction already read. Reject and rollback $T_i$.
• If TS(T_i) < W-timestamp(Q): $T_i$ is trying to write a value that was already overwritten by a younger transaction. Reject and rollback $T_i$.
• Otherwise: Allow the write. Update W-timestamp(Q) = TS(T_i).

2. Thomas' Write Rule

An optimization of the basic protocol. If TS(T_i) < W-timestamp(Q) for a write operation, instead of rolling back $T_i$, the system simply ignores the write (since it would have been overwritten anyway by the younger transaction). This reduces unnecessary rollbacks.

3. Advantages & Disadvantages

Advantages: Deadlock-free (no locks are used). Guarantees conflict serializability.

Disadvantages: Cascading rollbacks are possible. Starvation can occur if a transaction is repeatedly rolled back and restarted with a new timestamp.

4. Multiversion Concurrency Control (MVCC)

Modern databases (PostgreSQL, MySQL InnoDB, Oracle) use MVCC: each write creates a new version of the data item instead of overwriting it. Readers always see a consistent snapshot based on their transaction's start timestamp, so reads never block writes and writes never block reads.