Distributed Deadlock Detection in Distributed Database Systems
Tsai, Wang-Chuan
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69504
Description
Title
Distributed Deadlock Detection in Distributed Database Systems
Author(s)
Tsai, Wang-Chuan
Issue Date
1982
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
Deadlock detection in distributed database systems is very complicated and difficult to handle because of the distributed nature of the system and the communication delay of the network. Many detection algorithms have been proposed in the past, but most of them have been shown to be incorrect and inefficient. Designing an applicable algorithm is still worthy of intensive study.
In this thesis, a distributed deadlock detection algorithm is proposed. Checking a cycle in a graph, called an "RTR" graph, is used to detect a deadlock state. The inter-communication scheme of the algorithm generates and propagates "reaching" messages in order to update the RTR graphs at other sites. The reaching message is a fixed-size message containing a transaction node, a resource node and a timestamp. Timestamps are also attached to the graph edges in order to avoid false deadlocks. A deadlock recovery approach is also proposed to break deadlock after it is detected. A minimum cost policy and a "polling" synchronization scheme are used in the algorithm in order to break the detected deadlock state with a minimum communication cost.
A message generation scheme based on transaction ordering has been applied to the proposed deadlock detection algorithm to reduce the number of reaching messages transmitted and increase the efficiency of the deadlock detection. For a deadlock state with n transactions involved, this algorithm needs half the number of reaching messages of the original algorithm in the worst case.
The proposed algorithm has been shown to be correct and more efficient compared to previously proposed algorithms. It has been shown that the reaching message generation scheme of the algorithm will ensure the detection of all possible deadlocks, and the comparison of timestamps in graph edges and messages will prevent false deadlocks.
A simulator in PATH PASCAL has been written during the design of the algorithm for testing correctness and improving performance. Four network sites with I/O channels to the virtual network model have been simulated.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
