A Distributed Deadlock Detection Algorithm for CSP-Like Communication

Abstract

An algorithm for detecting deadlocks in distributed systems with CSP-like communication is proposed. Unlike previous work, the proposed algorithm avoids periodically sending deadlock-detecting messages by the processes and requires no local storage for the processes with size predetermined by the number of processes in the system. The algorithm is proven to have the following properties: (0) it never detects false deadlocks; (1) it has only one process in a knot report the deadlock; and (2) it detects every true deadlock in finite time.