D-algorithm application to DB

From: John Conover <john@email.johncon.com>
Subject: D-algorithm application to DB
Date: Sat, 21 Aug 1993 21:55:54 -0700 (PDT)

Consider the problem of deadlock in a distributed database system.
The database is assumed to be distributed on many computers, connected
together by a network. It is further assumed that many transactions
are permitted, concurrently, and that any transaction may involve
manipulation of the database(s) on any other computer(s) in the

The concurrency issues can be handled by classic two phase locking
(2PL,) (ie., acquire locks on all records, and EOF of all database
files-for phantom record considerations, prior to manipulating any
record in any database (1).) In a multi-user, distributed, concurrent
environment, this creates the possibility of a network wide,
distributed deadlock during the acquisition of the locks. Deadlock
arbitration could be handled by a central control process (in a
fashion similar to the client/server arbitration in a single machine
environment,) somewhere in the system, perhaps using wait-for-graphs
(WFG) techniques (2).

It seems that the concept of the D-algorithm (3) could be applied to
the problem, and would possibly eliminate the necessity of a central
control process. Since the D-algorithm is used for fault detection in
edge triggered digital circuits, which seems like a similar problem,
perhaps there is some applicability.

1. "Concurrency Control and Recovery in Database Systems," P.A.
Bernstein, V. Hadzilacos, N. Goodman, Addison Wesley, 1987, ISBN
0-201-10715-5, pp. 47

2. Bernstein, et al, pp. 79.

3. "Advanced Simulation and Test Methodologies for VLSI Design,"
Gordon Russell, Ian L. Sayers, Van Nostrand Reinhold, 1989, ISBN 0
7476 0001 5, pp. 110.

Copyright © 1993 John Conover, john@email.johncon.com. All Rights Reserved.
Last modified: Fri Mar 26 18:58:57 PST 1999 $Id: 930822045555.969.html,v 1.0 2001/11/17 23:05:50 conover Exp $
Valid HTML 4.0!