Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Timestamp-based concurrency control
Summary
In computer science, a timestamp-based concurrency control algorithm is a non-lock concurrency control method. It is used in some databases to safely handle transactions, using timestamps.
Every timestamp value is unique and accurately represents an instant in time.
A higher-valued timestamp occurs later in time than a lower-valued timestamp.
A number of different ways have been used to generate timestamp
Use the value of the system's clock at the start of a transaction as the timestamp.
Use a thread-safe shared counter that is incremented at the start of a transaction as the timestamp.
A combination of the above two methods.
Each transaction () is an ordered list of actions (). Before the transaction performs its first action (), it is marked with the current timestamp, or any other strictly totally ordered sequence: . Every transaction is also given an initially empty set of transactions upon which it depends, , and an initially empty set of old objects which it updated, .
Each object in the database is given two timestamp fields which are not used other than for concurrency control: is the time at which the value of object was last used by a transaction, is the time at which the value of the object was last updated by a transaction.
For all :
For each action :
If wishes to use the value of :
If then abort (a more recent thread has overwritten the value),
Otherwise update the set of dependencies and set ;
If wishes to update the value of :
If then abort (a more recent thread is already relying on the old value),
If then skip (the Thomas Write Rule),
Otherwise store the previous values, , set , and update the value of .
While there is a transaction in that has not ended: wait
If there is a transaction in that aborted then abort
Otherwise: commit.
To abort:
For each in
If equals then restore and
Whenever a transaction begins, it receives a timestamp. This timestamp indicates the order in which the transaction must occur, relative to the other transactions.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.