A fast algorithm for detecting distributed deadlocks in the OR request model

This paper presents a deadlock detection algorithm under the OR request model in distributed systems. The initiator of the algorithm constructs a reduced wait-for graph through propagation of probes and receiving replies directly from the processes involved in the execution. A scheme of encoding path information from the initiator to each process is developed so that blocking relationship between processes is deduced at the initiator rather than explicitly sent to the initiator. This helps reduce the amount of information carried by the reply messages. Time complexity is improved to d as compared to 2d in the current best algorithms, where d is the diameter of the wait-for graph. All deadlocks reachable from the initiator are resolved, whereas the current algorithms only know if the initiator is in deadlock. A unique property of the algorithm is that it handles concurrent algorithm executions and prevents duplicate deadlock detection which may cause false deadlock resolution, whereas most existing algorithms ignore this issue and deal with single execution of the algorithm only