Two-Phase Deadlock Detection Algorithm

A. K. Elmagarmid, A. K. Datta

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

In this paper, a deadlock detection algorithm utilizing a transaction-wait-for (TWF) graph is presented. It is a fully distributed algorithm which allows multiple outstanding requests. The proposed algorithm can achieve improved overall performance, using multiple disjoint controllers coupled with the two-phase property, while maintaining the simplicity of centralized schemes. The detection step is divided into two phases. Phase 1 analyzes the conditions of the system of interacting transactions, involving phase 2 only if conditions are possible for deadlocks to occur. Phase 2 performs the actual cycle detection. The proposed algorithm can be used in transaction based distributed processing systems. Some results on the complexity of the algorithm are given.

Original languageEnglish
Pages (from-to)1454-1458
Number of pages5
JournalIEEE Transactions on Computers
Volume37
Issue number11
DOIs
Publication statusPublished - Nov 1988
Externally publishedYes

Keywords

  • Database systems
  • deadlock detection
  • distributed processing
  • nested transactions
  • operating systems

Fingerprint

Dive into the research topics of 'Two-Phase Deadlock Detection Algorithm'. Together they form a unique fingerprint.

Cite this