Distributed deadlock detection and resolution by dynamic process grouping

Abstract

The problem of detecting resource deadlocks(alos called AND-deadlock) in a distributed environment is considered in this thesis. Two algorithms based on the concept of grouping which synamically divide the transactions in the system into a set of gruops are presented. The proposed algorithms assign group label to each transcation such that the group labels contain dependency and distance information among transactions within a group. The group label for each transaction is dynamically changed during run-time according to configuration changes in the wait-for-graph(WFG). The first algorithm is based on exclusive lock model where a transcation``s request for a data item can conflict with at most one other request, which means the maximum outdegree of the WFG is 1. In this algorithm, group labels are assigned such that the group labels for any pair of transactions within a group always define their dependency. The second algorithm is based on more general model where a node in the WFG can have multiple outgoing deges. With this assumption, the second algorithm employs another distributed scheme which dynamically assigns gruop label to each transaction. The algorithm uses two-level ordering-group ordering and local ordering-to establish a total ordering among transactions in the system. Group ordering is used to effectively reduce the number of probes to detect a deadlock and local ordering is used to decide whether a transaction is deadlocked or not. Since the dependency information between transactions are updated during run-time, there is no separate "detection phase" in the proposed algorithms. The algorithms ensure that only one transaction within a cycle detects the deadlock, which simplified the problem of deadlock resolution. The deadlock resolution precedure is very simple compared to that of existing solutions. The dependency infromation remains valid after the resolution of a deadlock. Therefore, the detection of future deadlocks can be done with less ef...