A Distributed Deadlock Detection Algorithm and Its Correctness Proof.

摘要

This paper presents a very simple distributed algorithm for deadlock detection in a network of processes. The algorithm is proven correct, i.e., we show that all true deadlocks are detected and no false reporting of deadlock occurs. In the algorithm no process maintains global information. All messages have identical length and are short, consisting of a single node name and a sequence number. Work is based on the work of Dijkstra and Scholten on termination detection of diffusing computations.