• A schedule in which the transactions participate is serializable, and the equivalent serial schedule has the transactions in order of their timestamp values. This is called timestamp ordering (TO).

• Notice how this differs from 2PL, where a schedule is serializable by being equivalent to some serial schedule allowed by the locking protocols.

• In timestamp ordering, however, the schedule is equivalent to the particular serial order corresponding to the order of the transaction timestamps.

• The algorithm must ensure that, for each item accessed by conflicting operations in the schedule, the order in which the item is accessed does not violate the serializability order.

• To do this, the algorithm associates with each database item X two timestamp (TS) values:

1. Read_TS(X): The read timestamp of item X; this is the largest timestamp among all the timestamps of transactions that have successfully read item X—that is, read_TS(X) = TS(T), where T is the youngest transaction that has read X successfully.

2. Write_TS(X): The write timestamp of item X; this is the largest of all the timestamps of transactions that have successfully written item X—that is, write_TS(X) = TS(T), where T is the youngest transaction that has written Xsuccessfully.

Basic Timestamp Ordering

• Whenever some transaction T tries to issue a read_item(X) or a write_item(X) operation, the basic TO algorithm compares the timestamp of T with read_TS(X) and write_TS(X) to ensure that the timestamp order of transaction execution is not violated.

• If this order is violated, then transaction T is aborted and resubmitted to the system as a new transaction with a new timestamp.

• If T is aborted and rolled back, any transaction T1 that may have used a value written by T must also be rolled back. Similarly, any transaction T2 that may have used a value written by T1 must also be rolled back, and so on.

• This effect is known as cascading rollback and is one of the problems associated with basic TO, since the schedules produced are not recoverable.

• An additional protocol must be enforced to ensure that the schedules are recoverable, cascade less, or strict. We first describe the basic TO algorithm here.

• The concurrency control algorithm must check whether conflicting operations violate the timestamp ordering in the following two cases:

a. Transaction T issues a write_item(X) operation:

o If read_TS(X) >TS(T) or if write_TS(X) > TS(T), then abort and roll back T and reject the operation. This should be done because some younger transaction with a timestamp greater than TS(T)—and hence after T in the timestamp ordering has already read or written the value of item X before T had a chance to write X, thus violating the timestamp ordering.

o If the condition in part (a) does not occur, then execute the write_item(X) operation of T and set write_TS(X) to TS(T).

b. Transaction T issues a read_item(X) operation:

o If write_TS(X) >TS(T), then abort and roll back T and reject the operation. This should be done because some younger transaction with timestamp greater than TS(T)—and hence after T in the timestamp ordering—has already written the value of item X before T had a chance to read X.

o If write_TS(X) <= TS(T), then execute the read_item(X) operation of T and set read_TS(X) to the larger of TS(T) and the current read_TS(X).

• Hence, whenever the basic TO algorithm detects two conflicting operations that occur in the incorrect order, it rejects the later of the two operations by aborting the transaction that issued it.

• The schedules produced by basic TO are hence guaranteed to be conflict serializable, like the 2PL protocol.

• However, some schedules are possible under each protocol that is not allowed under the other. Hence, neither protocol allows all possible serializable schedules.

• As mentioned earlier, deadlock does not occur with timestamp ordering. However, cyclic restart (and hence starvation) may occur if a transaction is continually aborted and restarted.

Strict Timestamp Ordering

• A variation of basic TO called strict TO ensures that the schedules are both strict (for easy recoverability) and (conflict) serializable.

• In this variation, a transaction T that issues a read_item(X) or write_item(X) such that TS(T) >write_TS(X) has its read or write operation delayed until the transaction T that wrote the value of X (hence TS(T) = write_TS(X)) has committed or aborted.

• To implement this algorithm, it is necessary to simulate the locking of an item X that has been written by transaction T until T is either committed or aborted. This algorithm does not cause deadlock, since T waits for T only if TS(T) > TS(T).

Thomas's Write Rule

A modification of the basic TO algorithm, known as Thomas’s write rule, does not enforce conflict serializability; but it rejects fewer write operations, by modifying the checks for the write_item(X) operation as follows:

i. If read_TS(X) >TS(T), then abort and roll back T and reject the operation.

ii. If write_TS(X) >TS(T), then do not execute the write operation but continue processing. This is because some transaction with timestamp greater than TS(T)—and hence after T in the timestamp ordering—has already written the value of X.

Hence, we must ignore the write_item(X) operation of T because it is already outdated and obsolete. Notice that any conflict arising from this situation would be detected by case (i).

iii. If neither the condition in part (i) nor the condition in part (ii) occurs, then execute the write_item(X) operation of T and set write_TS(X) to TS(T).