Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

PROBABILISTIC TECHNIQUES FOR TWO PHASE LOCKING IN DATABASE SYSTEMS

IP.com Disclosure Number: IPCOM000149378D
Original Publication Date: 1983-Oct-31
Included in the Prior Art Database: 2007-Apr-01

Publishing Venue

Software Patent Institute

Related People

Spirakis, Paul: AUTHOR [+3]

Abstract

PROBABILISTIC TECHNIQUES FOR TWO PHASE LOCKING IN DATABASE SYSTEMS* BY Paul Spirakis (l) and John Reif (2) October 1983 Report 8102 *This work was partially supported by the NSF Grant MCS 83-00630 (l'courant Institute of Mathematical Sciences, New York University (2)~iken Computation Laboratory, Barvard University #.. Abstract Two phase locking (2PL) is one of the few important techniques used for database concurrency control. It has the feature that as soon as a transaction releases a lock, it never obtains additional locks. The two phase locking protocol guarantees serializability of transaction executions, hence it is a correct synchronization technique. One of the most common variations of 2PL is static locking (SL) where a transaction is allowed to act on the data only if all the locks it needs are granted t.o it. The main advantage of SL is that deadlocks are avoided. Although some investigators provided lately quantitative analyses os the performance of locking, most of the analyses use very strong assumptions about transaction arrivals and transaction behavior, in order to overcome the difficulties of modelling transaction interference. In some cases, the analytic results provide little intuition about the degradation of performance due to locking.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 16

PROBABILISTIC TECHNIQUES FOR TWO PHASE LOCKING
IN DATABASE SYSTEMS*

          BY
Paul Spirakis
(l) and John Reif (2)

October 1983 Report 8102

*This work was partially supported by the NSF Grant MCS 83-00630
(l'courant Institute of Mathematical Sciences, New York University
(2)~iken Computation Laboratory, Barvard University

#..

[This page contains 1 picture or other non-text object]

Page 2 of 16

[This page contains 1 picture or other non-text object]

Page 3 of 16

Abstract

    Two phase locking (2PL) is one of the few important techniques
used for database concurrency control. It has the feature that as
soon as a transaction releases a lock, it never obtains additional
locks. The two phase locking protocol guarantees serializability
of transaction executions, hence it is a correct synchronization
technique. One of the most common variations of 2PL is static
locking (SL) where a transaction is allowed to act on the data only
if all the locks it needs are granted t.o it. The main advantage of
SL is that deadlocks are avoided.

    Although some investigators provided lately quantitative
analyses os the performance of locking, most of the analyses use
very strong assumptions about transaction arrivals and transaction
behavior, in order to overcome the difficulties of modelling
transaction interference. In some cases, the analytic results
provide little intuition about the degradation of performance due
to locking.

    In this paper, we propose a new implementation of 2PL. Our
implementation is suited for a distributed database system, since
there is no need of a central scheduler of transaction actions. The
main innovation of the technique is the use of probabilistic choice
within the 2PL protocol, toachieve fast transaction response time.
Our proposed implementation is similar to a static 2PL in the
sense that transactions are allowed to operate on the data only when
all locks are obtained.

    Another contribution of the paper is that we give a tractable
analysis for the mean response time of t:ransactions and bounds for
the distribution of the response time. Our analysis does not need
oversimplifying assumptions on transaction behavior (e.~.
uniform

data reference or Poisson arrivals).

    We apply randomization to 2PL protocols in stages of increasing
sophistication (and efficiency), starting from a straiqht-forward
use of random waits and advancing to a technique of probabilistic
bidding for locks and then aiving a technique which combines the
above uses of random choice in order to favor transactions with
readsets of small cardinality. We show our bidding technique to
be optimal for distributed SL in the sense of matching lower bounds
for transaction response time. We brieflv mention an extension of
our techniques to qet an efficient implementation of Moss's 2PL
protocol for nested transactions.

[This page contains 1 picture or other non-text object]

Page 4 of 16

1. Introduc...