As we have seen above, a problem with 2PL is that it can lead to deadlocks. Reed's multiversion timestamp ordering scheme solves this problem by ordering transactions and aborting transactions that access data out of order. It also increases the concurrency in the system by never making an operation block (though it does abort transactions.)
It assigns transactions timestamps when they are started,
which are used to order these transactions.
Moreover,
it associates each data item
with
timestamped versions and associates each version with
readtimestamps.
A readtimestamp is associated with a data item whenever a transaction
reads the data item and is the same as the timestamp of the reading transaction.
A timestamped version is created whenever a transaction writes
a new value to the data item and has the timestamp of the writing transaction.
The following steps occur when a transaction accesses the database:
If the operation is a read,
then it is allowed,
and the version read is the one with the largest timestamp less
than the timestamp of the reading transaction.
The timestamp of the reading transaction is added to the item.
If the operation is a write,
then a new version of the data item is created with the timestamp
of the writing transaction as long as no transaction with a more recent
timestamp has read a version of the item with an older timestamp than
that of the writing transaction. If this check fails,
the writing transaction is aborted and restarted.
This approach will support the schedule shown in Figure 1 by making
sure T2 sees the values written by T1.