DBMS Menu

Timestamp Based Protocols in DBMS



Timestamp-based protocols are concurrency control mechanisms used in databases to ensure serializability and to avoid conflicts without the need for locking. The main idea behind these protocols is to use a timestamp to determine the order in which transactions should be executed. Each transaction is assigned a unique timestamp when it starts.

Here are the primary rules associated with timestamp-based protocols:

1. Timestamp Assignment: When a transaction \( T \) starts, it is given a timestamp \( TS(T) \). This timestamp can be the system's clock time or a logical counter that increments with each new transaction.

2. Reading/Writing Rules: Timestamp-based protocols use the following rules to determine if a transaction can read or write an item:

  • Read Rule: If a transaction \( T \) wants to read an item that was last written by transaction \( T' \) with \( TS(T') > TS(T) \), the read is rejected because it's trying to read a value from the future. Otherwise, it can read the item.
  • Write Rule: If a transaction \( T \) wants to write an item that has been read or written by a transaction \( T' \) with \( TS(T') > TS(T) \), the write is rejected. This avoids overwriting a value that has been read or written by a younger transaction.

3. Handling Violations: When a transaction's read or write operation violates the rules, the transaction can be rolled back and restarted or aborted, depending on the specific protocol in use.


Let's look at examples to better understand these rules:

Example on Timestamp-based protocols

Suppose two transactions \( T1 \) and \( T2 \) with timestamps 5 and 10 respectively:

  1. \( T1 \) reads item \( A \).
  2. \( T2 \) writes item \( A \).
  3. \( T1 \) tries to write item \( A \).

According to the write rule, \( T1 \) can't write item \( A \) after \( T2 \) has written it, because \( TS(T2) > TS(T1) \). Thus, \( T1 \)'s write operation will be rejected.

Example-2

Suppose two transactions \( T1 \) and \( T2 \) with timestamps 5 and 10 respectively:

  1. \( T2 \) writes item \( A \).
  2. \( T1 \) tries to read item \( A \).

According to the read rule, \( T1 \) can't read item \( A \) after \( T2 \) has written it, as \( TS(T2) > TS(T1) \). So, \( T1 \)'s read operation will be rejected.

Advantages of Timestamp-based Protocols

  1. Deadlock-free: Since there are no locks involved, there's no chance of deadlocks occurring.
  2. Fairness: Older transactions have priority over newer ones, ensuring that transactions do not starve and get executed in a fair manner.
  3. Increased Concurrency: In many situations, timestamp-based protocols can provide better concurrency than lock-based methods.

Disadvantages of Timestamp-based Protocols

  1. Starvation: If a transaction is continually rolled back due to timestamp rules, it may starve.
  2. Overhead: Maintaining and comparing timestamps can introduce overhead, especially in systems with a high transaction rate.
  3. Cascading Rollbacks: A rollback of one transaction might cause rollbacks of other transactions.

One of the most well-known timestamp-based protocols is the Thomas Write Rule, which modifies the write rule to allow certain writes that would be rejected under the basic timestamp protocol. The idea is to ignore a write that would have no effect on the outcome, rather than rolling back the transaction. This reduces the number of rollbacks but can result in non-serializable schedules.

In practice, timestamp-based protocols offer an alternative approach to concurrency control, especially useful in systems where locking leads to frequent deadlocks or reduced concurrency. However, careful implementation and tuning are required to handle potential issues like transaction starvation or cascading rollbacks.

Next Topic :Validation Based Protocols in DBMS