Local distributed deadlock detection by knot detection

Abstract

A distributed algorithm for the detection of deadlocks in slore-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most O(n' + m) messages and O( log(n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which came the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.