Browse Prior Art Database

Distributed Optimistic Concurrency Control Based On Time-Stamp History Certification

IP.com Disclosure Number: IPCOM000102628D
Original Publication Date: 1990-Dec-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 4 page(s) / 157K

Publishing Venue

IBM

Related People

Dias, DM: AUTHOR [+2]

Abstract

A time-stamp-based certification scheme that uses time-stamp history information to significantly reduce transaction aborts due to read- write conflicts in a centralized complex under a single Concurrency Control (CC) manager is described in (1). This is referred to as certification with adaptive time stamp selection. Here, the adaptive time stamp scheme is generalized to a distributed environment where there are multiple processing nodes interconnected by a network and the databases are partially replicated over the multiple nodes. We assume that among the multiple sites with a copy of a database, one of them is designated as the master (primary) site.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Distributed Optimistic Concurrency Control Based On Time-Stamp History Certification

       A time-stamp-based certification scheme that uses
time-stamp history information to significantly reduce transaction
aborts due to read- write conflicts in a centralized complex under a
single Concurrency Control (CC) manager is described in (1).  This is
referred to as certification with adaptive time stamp selection.
Here, the adaptive time stamp scheme is generalized to a distributed
environment where there are multiple processing nodes interconnected
by a network and the databases are partially replicated over the
multiple nodes.  We assume that among the multiple sites with a copy
of a database, one of them is designated as the master (primary)
site.

      In this method, at transaction commit time, the local CC
manager (at the site where the transaction runs), referred to as the
coordinator, assigns a globally unique time-stamp to the transaction
denoted as transaction X.  It then communicates with the master sites
of data items accessed by transaction X to find out whether the
transaction can be committed with that time stamp or with an
alternative time stamp to be determined, or whether the transaction
must be aborted.  The CC manager at each participating master site
checks the transaction time stamp against the read or write time
stamp of the data items accessed as defined below.  A read time stamp
(Tr) and write time stamp (Tw) are maintained for each data item.
The read time-stamp is the time-stamp of the youngest (i.e., latest
in time) committed transaction which read the data.  The write
time-stamp is the time-stamp of the youngest committed transaction
which updated the data.  In addition, k update history time-stamps
(T1,...,Twk) are maintained for the data, with Tw1 as the time-stamp
of the oldest update and Tk as that of

                            (Image Omitted)

 the latest update, so that Tw = Twk .  A transaction views each
data item as a (name, version) pair.  For each data item read, we
track the Tw of the data as its version.  Assume that transaction X
is given a time stamp Ts .  For each data item Dri read, i =
1,...,m, the version read is checked with the current Tw of the data
item.  If all match, we further check whether Ts is larger than the
read time-stamp of each updated item.  If this condition holds, the
transaction can be certified.  In the basic time-stamp-based
certification scheme (2), the transaction is aborted if the above
condition is not satisfied, i.e., if all matches did not occur.  The
next paragraph describes how we avoid unnecessary aborts that this
gives rise to.

      First consider the case when some of the data items read are
not the up-to-date version.  If some data items, say Dri, i =
1,...,m, do not have their version numbers equal to Tw(Dri), it
simply means those data items have been updated subsequently by other
transactions.  We then c...