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 system. 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.