1
7.8kviews
Explain the basic timestamp ordering algorithm
1 Answer
1
246views

• 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.

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

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

    a. 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 henceafter 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.

    b. 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).

  2. Transaction T issues a read_Item(X) operation:

    a. 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.

    b. If write_TS(X) a 13(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).

Please log in to add an answer.