Timestamp Based and Validation Based Protocols

Definition

Timestamp-based protocol is a concurrency control method in which every transaction is assigned a unique timestamp, and the protocol ensures that conflicting read/write operations are executed in timestamp order so that the resulting schedule is equivalent to a serial schedule based on timestamps.

Validation-based protocol is a concurrency control method in which transactions execute without immediate locking or conflict checking, and before commit, each transaction is validated to determine whether it conflicts with other concurrent transactions; only validated transactions are allowed to commit.

Main Content

1. First Concept

Timestamp Based Protocol

Every transaction gets a timestamp when it begins, usually based on the system clock or a logical counter.
The timestamp determines the priority/order of the transaction. An older transaction must be allowed to act before a younger one when both conflict on the same data item.

Key Working Idea

If transaction T1 has timestamp 10 and transaction T2 has timestamp 20, then T1 is older and should be treated as having higher priority in conflict situations.
This avoids the need for locks, but the database must maintain two timestamps for each data item:
Read Timestamp (RTS): the largest timestamp of any transaction that successfully read the item.
Write Timestamp (WTS): the largest timestamp of any transaction that successfully wrote the item.

Example

Suppose data item X has:

RTS(X) = 5
WTS(X) = 7

If a transaction with timestamp 6 wants to write X, the system checks whether that action violates timestamp order. If it does, the operation is rejected or the transaction is rolled back.

Important Features

No waiting due to locks, so deadlocks do not occur.
Conflicting operations are forced to respect timestamp order.
Transactions may be rolled back if they try to violate the order.

2. Second Concept

Validation Based Protocol

Also known as optimistic concurrency control, because it assumes conflicts are rare.
Transactions are allowed to execute their operations on local copies or working versions without locking the database during the execution phase.
At commit time, the transaction is checked against other transactions to see whether its actions can be safely accepted.

Phases of Validation Based Protocol

Read phase

: transaction reads data and performs updates on its private workspace.

Validation phase

: system checks whether the transaction conflicts with others.

Write phase

: if validation succeeds, the transaction’s changes are permanently written to the database.

Validation Rules

A transaction is validated based on whether:

It has read data written by another transaction that committed before it.
It overlaps unsafely with transactions that are still active.
Its read and write sets conflict with other committed or concurrent transactions.

Example

Transaction T1 reads A and B, then computes a new value for C. If another transaction T2 modifies A before T1 commits, the validation step checks whether T1’s result is still correct. If not, T1 is aborted and restarted.

Important Features

No locking during normal execution.
Suitable when conflicts are low.
May waste work if many transactions fail validation late in execution.

3. Third Concept

Comparison Between Timestamp Based and Validation Based Protocols

Control method

:
Timestamp-based: controls concurrency continuously during read and write operations.
Validation-based: controls concurrency mainly at commit time.

Conflict handling

:
Timestamp-based: conflicts are detected immediately when an operation occurs.
Validation-based: conflicts are detected after execution during validation.

Rollback behavior

:
Timestamp-based: may abort a transaction when it performs an invalid operation.
Validation-based: transaction may run to completion and then fail validation.

Deadlock

:
Timestamp-based: deadlocks do not occur because no waiting on locks.
Validation-based: deadlocks do not occur because no locking is used for concurrency control.

Performance

:
Timestamp-based: better when conflicts are moderate and quick enforcement is needed.
Validation-based: better when conflicts are rare and most transactions can commit successfully.

ASCII Diagram for Comparison

Transaction flow comparison:

Timestamp-Based:
T1 -----> checked at each operation -----> commit
T2 -----> checked at each operation -----> commit

Validation-Based:
T1 -----> execute freely -----> validate -----> commit/abort
T2 -----> execute freely -----> validate -----> commit/abort

Practical Observation

Timestamp-based protocols are strict and order-driven.
Validation-based protocols are flexible and optimistic.
Both aim to produce serializable schedules, but they do so in different ways.

Working / Process

1. Transaction arrival and ordering

In timestamp-based protocols, each transaction receives a unique timestamp at the start.
In validation-based protocols, the transaction begins execution normally without immediate ordering restrictions.
The system keeps track of active transactions and their data access sets.

2. Execution and conflict checking

In timestamp-based protocols, every read or write is checked against the timestamps of the data item.
A read is allowed only if it does not violate the write order.
A write is allowed only if it does not violate older reads or writes.
In validation-based protocols, the transaction reads data, makes changes in a private workspace, and records its read set and write set.
At commit time, the system compares these sets with other transactions to detect conflicts.

3. Commit, abort, or restart

If a timestamp rule is violated, the transaction is aborted and may be restarted with a new timestamp.
If validation succeeds, the private changes are written to the database and the transaction commits.
If validation fails, the transaction is rolled back and restarted later if needed.

Diagram for Process

Start transaction
       |
       v
Assign timestamp / begin execution
       |
       v
Check operation rules or collect read-write sets
       |
       v
Validate or compare timestamps
       |
       +--> Success --> Commit
       |
       +--> Failure --> Abort and restart

Advantages / Applications

Prevents inconsistent updates in concurrent environments

Both protocols help maintain correctness when multiple users access the same data simultaneously.
They ensure that the final result is equivalent to some serial order of transactions.

No deadlock problem

Since these approaches do not depend on traditional lock waiting, deadlocks are avoided.
This is especially useful in systems with many transactions and high concurrency.

Useful in different workload environments

Timestamp-based protocols are suitable when a strict order is needed and operations must be controlled continuously.
Validation-based protocols are suitable when conflicts are rare and transactions usually complete successfully.

Applications

Banking systems where transfer and balance-update operations must remain correct.
Reservation systems such as airline or hotel bookings.
Online transaction processing systems with many concurrent users.
Database engines that need efficient concurrency without heavy locking overhead.

Summary

Timestamp based protocols control transactions using assigned time order.
Validation based protocols allow execution first and check correctness before commit.
Both are used to keep database transactions serializable and consistent.
Important terms to remember: timestamp, read timestamp, write timestamp, validation, read phase, write phase, serializability