DISTRIBUTED DEADLOCK DETECTION/RESOLUTION BASED ON THE DYNAMIC WFG

摘要

In literature, most distributed deadlock detection algorithms only described how to search cycle or knot in a wait-for graph (WFG). However, the blocking transaction creating, quitting and the machine or the communication channel failures in the system would lead to the dynamic changing of the WFG How the multi detections run concurrently under these circumstances has not been considered. In this paper, a new generalized distributed deadlock detection algorithm is proposed, in where the system changing is reflected as the node appearing or disappearing in a dynamic WFG (DWFG). Both of the active and passive node quitting is defined as the termination conditions of a detection process, and then the concurrent running detection processes can terminate in turn. The algorithm can tolerate three kinds of failures. The correctness of the algorithm is proven. Performance evaluation shows the timing and message complexity of our algorithm outperforms the existing algorithms under the static WFG.