Timestamp Based Algorithms

by

Girish Saligram

In timestamp based concurrency control algorithms, each site maintains a logical clock. This clock is incremented when a transaction is submitted at that site and updated whenever the site receives a message with a higher clock value. Each transaction is assigned a unique timestamp and conflicting actions are executed in order of the timestamp of their transactions.

Timestamps can be used in two ways:

  • To determine the currency or outdatedness of a request with respect to the data object it is operating on.
  • To order events with respect to one another.

    In timestamp based concurrency control algorithms , the serialization order of transactions is selected a priori, and transactions are forced to follow this order.

    Basic Timestamp Ordering Algorithm(BTO)

    We assume that the Transaction Manager (TM) attaches an appropriate timestamp to all read and write operations. In the BTO, the scheduler at each Data Manager (DM), keeps track of the largest timestamp of any read and write operation processed thus far for each data object. These timestamps may be denoted by R-ts(object) and W-ts(object), respectively. Let us also make the following notations:
    read(x,TS) --> Read request with timestamp TS on a data object x.
    write(x,v,TS) --> Write request with timestamp TS on a data object x. v is the value to be assigned to x.

    A read request is handled in the following manner:
    If TS < W-ts(x) then

    reject read request and abort corresponding transaction
    else
    execute transaction
    Set R-ts(x) to max{R-ts(x), TS}

    A write request is handled in the following manner:
    If TS < R-ts(x) or TS < W-ts(x) then

    reject write request
    else
    execute transaction
    Set W-ts(x) to TS.

    If a transaction is aborted, it is restarted with a new timestamp. This can result in a cyclic restart where a transaction can repeatedly restart and abort without ever completing. Another disadvantage is that it has storage overhead for maintaining timestamps ( two timestamps must be kept for every data object).

    References:

  • Singhal, Mukesh, & Shivaratri, N. G., "Advanced Concepts in Operating Systems", Chapter 20, pp506.
    Go Back to the Operating Systems page.
    saligram@csgrad.cs.vt.edu