Kadaba Bharath-Kumar, Jeffrey M. Jaffe
IEEE Transactions on Communications
A distributed algorithm for the detection of deadlocks in store-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(n2+ m) messages and O(log (n)) bits of memory to detect alldeadlocked 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 cause 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. Copyright © 1987 by the Institute of Electrical and Electronics Engineers, Inc.
Kadaba Bharath-Kumar, Jeffrey M. Jaffe
IEEE Transactions on Communications
Israel Cidon, Roch Guérin, et al.
Probab. Eng. Inf. Sci.
Israel Cidon
IEEEI 1991
Jeffrey M. Jaffe, Adrian Segall
IEEE Transactions on Communications