An Efficient Generalized Deadlock Detection and Resolution Algorithm in Distributed Systems

摘要

In this paper we propose a distributed deadlock detection algorithm on the basis of history-based edge chasing which resolves the deadlock as soon as detects it without waiting for the probe to return back. This action reduces the average persistence time of the deadlock in compare with other similar algorithms in distributed systems. Our proposed algorithm detects and resolves the deadlocks, whether the initiator directly or indirectly involves them and the useless messages in simultaneous execution of the algorithm are avoided by giving the priorities to the processes. It can also manage the simultaneous execution of the algorithm by its unique characteristic, using other nodes involved in deadlocks and prevents the detection of same deadlocks. We also minimized the information being carried in the probe offering a method to encode the information existed in probe in our suggested algorithm. Our algorithm is comparable with the best algorithms in case of its time complexity, the number of the messages and its efficiency.