Basic Timestamp Ordering Scheduler (BTO-SC) Algorithm

Concurrency control is one of the most important responsibilities of a database management system (DBMS). In a multi-user environment, several transactions may execute simultaneously, and without proper coordination, data inconsistency and corruption may occur.

To solve this problem, database systems use various concurrency control techniques, such as:

• Lock-based protocols
• Timestamp ordering protocols
• Validation-based protocols

Among these, the Basic Timestamp Ordering Scheduler (BTO-SC) is one of the most fundamental timestamp-based concurrency control algorithms.

Core Idea: Transactions are executed according to their timestamps so that the schedule remains serializable and conflict-free.

---

Why Concurrency Control is Necessary

Consider two banking transactions executing simultaneously:

T1: Withdraw ₹100 from Account A
T2: Deposit ₹500 into Account A

If both transactions execute without coordination, the final balance may become incorrect due to:

• Lost updates
• Dirty reads
• Inconsistent retrievals

Concurrency control ensures that multiple transactions can execute safely while preserving database consistency.

---

Introduction to Timestamp Ordering

Timestamp Ordering is a concurrency control technique where every transaction is assigned a unique timestamp when it starts execution.

The timestamp determines the order in which transactions should logically execute.

Example

Transaction	Timestamp
T1	5
T2	10
T3	15

Smaller timestamp → Older transaction

The scheduler ensures that conflicting operations execute according to timestamp order.

---

What is the Basic Timestamp Ordering Scheduler?

The Basic Timestamp Ordering Scheduler (BTO-SC) is a protocol that guarantees serializability by ensuring that:

If TS(T1) < TS(T2),
then T1 must appear before T2 in the final schedule.

Instead of using locks, the system compares timestamps to determine whether an operation is allowed.

---

Key Data Structures Used in BTO-SC

For every data item X, the scheduler maintains two timestamps:

1. Read Timestamp (RTS(X))

RTS(X) stores the largest timestamp of any transaction that has successfully read X.

2. Write Timestamp (WTS(X))

WTS(X) stores the largest timestamp of any transaction that has successfully written X.

---

Working Principle of BTO-SC

Whenever a transaction performs a read or write operation, the scheduler checks timestamp conditions.

If the operation violates timestamp order, the transaction is aborted and restarted.

---

Read Operation Rules

Suppose transaction Ti wants to read data item X.

Condition 1

TS(Ti) < WTS(X)

This means a newer transaction has already written X.

If Ti reads X now, it would see an outdated value, violating serializability.

Action

• Reject read operation
• Abort transaction Ti
• Restart Ti with a new timestamp

---

Condition 2

TS(Ti) ≥ WTS(X)

The read operation is safe.

Action

RTS(X) = max(RTS(X), TS(Ti))

The transaction is allowed to read X.

---

Write Operation Rules

Suppose transaction Ti wants to write data item X.

---

Case 1

TS(Ti) < RTS(X)

A newer transaction has already read X.

Allowing Ti to write would violate timestamp order because an older transaction would overwrite a value already observed by a newer transaction.

Action

• Abort Ti

---

Case 2

TS(Ti) < WTS(X)

A newer transaction has already written X.

Allowing Ti to write would overwrite newer data with older data.

Action

• Abort Ti

---

Case 3

If neither condition is true:

TS(Ti) ≥ RTS(X)
AND
TS(Ti) ≥ WTS(X)

Then writing is safe.

Action

WTS(X) = TS(Ti)

---

Detailed Example of BTO-SC

Assume:

TS(T1) = 5
TS(T2) = 10

Initial values:

RTS(X) = 0
WTS(X) = 0

---

Step 1: T1 Reads X

Check:

TS(T1) ≥ WTS(X)
5 ≥ 0 → TRUE

Read is allowed.

Update:

RTS(X) = 5

---

Step 2: T2 Writes X

Check:

TS(T2) < RTS(X)
10 < 5 → FALSE

TS(T2) < WTS(X)
10 < 0 → FALSE

Write is allowed.

Update:

WTS(X) = 10

---

Step 3: T1 Writes X

Check:

TS(T1) < RTS(X)
5 < 5 → FALSE

TS(T1) < WTS(X)
5 < 10 → TRUE

Violation occurs.

Action

• T1 is aborted

The older transaction T1 cannot overwrite data already modified by newer transaction T2.

---

Why BTO-SC Guarantees Serializability

All conflicting operations are forced to execute according to timestamp order.

Therefore:

• Cycles cannot form in the precedence graph
• Schedules remain conflict serializable

---

Advantages of BTO-SC

No Deadlocks

Since locks are not used, deadlocks are impossible.

---

High Parallelism

Transactions can execute concurrently without waiting for locks.

---

Simple Conflict Detection

Only timestamp comparisons are required.

---

Disadvantages of BTO-SC

Frequent Transaction Aborts

Older transactions may repeatedly restart.

---

Starvation

Some transactions may never complete due to continuous aborts.

---

Wasted Computation

Aborted transactions lose all work and must restart.

---

Thomas Write Rule (Improvement)

A major improvement over basic timestamp ordering is the Thomas Write Rule.

Normally:

TS(Ti) < WTS(X)

causes abort.

Thomas Write Rule ignores obsolete writes instead of aborting the transaction.

This reduces unnecessary transaction rollbacks.

---

Comparison with Lock-Based Concurrency Control

Feature	BTO-SC	Lock-Based Protocol
Uses Locks	No	Yes
Deadlock	Impossible	Possible
Rollback Frequency	High	Lower
Concurrency	High	Moderate
Waiting	No waiting	Transactions may wait

---

Applications of Timestamp Ordering

Timestamp ordering protocols are used in:

• Distributed database systems
• Real-time transaction processing
• High-concurrency environments
• Multi-version concurrency control systems (MVCC)

The Basic Timestamp Ordering Scheduler (BTO-SC) is an important concurrency control protocol that ensures serializability using transaction timestamps.

Instead of locking data items, the scheduler:

• Assigns timestamps to transactions
• Checks read/write operations against timestamp rules
• Aborts transactions that violate ordering constraints

Its major strength lies in deadlock-free execution and high concurrency. However, frequent rollbacks remain a major drawback.

Despite its limitations, BTO-SC forms the theoretical foundation for many advanced concurrency control mechanisms used in modern distributed databases.

---

Happy Exploring!