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 language | English |
---|---|
Pages (from-to) | 1454-1458 |
Number of pages | 5 |
Journal | IEEE Transactions on Computers |
Volume | 37 |
Issue number | 11 |
DOIs | |
Publication status | Published - Nov 1988 |
Externally published | Yes |
Keywords
- Database systems
- deadlock detection
- distributed processing
- nested transactions
- operating systems