Efficient design and evaluation of distributed deadlock detection and resolution in generalized model

Abstract

Deadlock is one of the canonical problems in distributed systems. It arises naturally in distributed systems such as distributed databases, distributed operating systems and store and forward networks. In these systems, the data reside at multiple distributed locations, and the processes have to collaborate in order to perform a task. Deadlocks are very difficult to detect in distributed systems. This is so because no site has accurate knowledge about the system, and the every inter-site communication involves a finite and unpredictable delay. The existing generalized deadlock detection algorithms are grouped into two categories namely Centralized Algorithms and Distributed Algorithms. In the Centralized algorithms, the global state of the system is maintained at the single site, whereas in the Distributed algorithms, the information requires to determine a deadlock is maintained across multiple sites. But, both types of algorithms have some limitations. This thesis strives to develop algorithms that minimize the messages as well as their length for detecting deadlocks without compromising other performance measures such as deadlock duration and deadlock resolution time. The performance of all proposed generalized deadlock detection and resolution algorithms is assessed using discrete event simulation. A large stochastic object oriented simulator is developed using JAVA and used for this purpose throughout the thesis. Numerical results reveal that the proposed algorithm considerably improves the performance in terms of number of messages, message length and deadlock resolution time over the existing algorithms. newline newline newline