The title of this paper is an accurate and concise description of the algorithm presented. The authors describe two algorithms. The first one uses a knot detection algorithm to identify the nodes of a computer network that cause deadlock in a static environment. A static environment is one in which the state of the buffers of a node participating in the algorithm is frozen. This algorithm is used in a second algorithm that detects deadlocks in a dynamic environment. The paper gives a general description of the operation of both algorithms.
The basic algorithm is local in that it does not require all of the nodes of a network to participate in the algorithm. It is efficient in terms of both memory costs and communication costs. It uses O(log n) bits of memory per node and O(n′2 + m′) control messages in the worst case, where n′ is the number of potentially deadlocked nodes and m′ is the number of links that are attached to these nodes. The algorithm is started only when there is the potential for deadlock, finds all deadlocked nodes, and does not interfere with other processes at the nodes.
Appendices are included to provide formal descriptions of the algorithms with analyses of the communication and memory costs. There is also a proof that all nodes that cause a deadlock, and no others, are identified by the basic algorithm.
The fundamental concepts used in the algorithms are clearly presented. The only discrepancy is the identification of the figures. Fig. 1 (p. 6) should be Fig. 3 (p. 7) and vice versa. The algorithm should be of interest to those involved in the design of distributed systems.
