Two-Phase Deadlock Detection Algorithm in Distributed Databases.

Seiichi Kawazu, Susumu Minami, Kenji Itoh, Katsuni Teranaka: Two-Phase Deadlock Detection Algorithm in Distributed Databases. VLDB 1979: 360-367
  author    = {Seiichi Kawazu and
               Susumu Minami and
               Kenji Itoh and
               Katsuni Teranaka},
  editor    = {Antonio L. Furtado and
               Howard L. Morgan},
  title     = {Two-Phase Deadlock Detection Algorithm in Distributed Databases},
  booktitle = {Fifth International Conference on Very Large Data Bases, October
               3-5, 1979, Rio de Janeiro, Brazil, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1979},
  pages     = {360-367},
  ee        = {db/conf/vldb/KawazuMIT79.html},
  crossref  = {DBLP:conf/vldb/79},
  bibsource = {DBLP,}


There are two deadlock detection methods in a distributed database. One is centralized, and the other is distributed. In this paper a distributed method is discussed.

Sub-Wait-Graphs, which express the state of execution of transactions in individual sites, are introduced, and a sufficient condition for a global deadlock not to occur is given, based on the Sub- Wait-Graph. This sufficient condition makes it possible for a deadlock detection to be separated into two phases, local deadlock detection and global deadlock detection. Also, an efficient deadlock detection algorithm, which requires to be built and maintain only Sub-Wait-Graphs, is proposed, by making use of this property. The characteristics and effects of this algorithm are discussed.

Copyright © 1979 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Antonio L. Furtado, Howard L. Morgan (Eds.): Fifth International Conference on Very Large Data Bases, October 3-5, 1979, Rio de Janeiro, Brazil, Proceedings. IEEE Computer Society 1979
Contents BibTeX


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Databases. Berkeley Workshop 1978: 215-232 BibTeX

Referenced by

  1. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
  2. Ahmed K. Elmagarmid, Amit P. Sheth, Ming T. Liu: Deadlock Detection Algorithms in Distributed Database Systems. ICDE 1986: 556-564
  3. Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper). VLDB 1982: 62-76
  4. Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:07 2009