An improved, centralised algorithm for detection and resolution of distributed deadlock in the generalised model

摘要

In this paper, we present a new centralised algorithm to detect and resolve generalised deadlock in distributed systems. The initiator of this algorithm induces a directed spanning tree by diffusing the probe messages among its dependent processes. It then collects replies that carry the dependency information of the dependent process to determine a deadlock. Moreover, the initiator of this algorithm performs reduction once it receives a reply from an active process unlike the existing algorithms. Hence, it terminates the execution when it detects a deadlock without waiting for termination detection. We have asserted the correctness of the algorithm formally. It has a worst-case time complexity of d + 2 time units, message complexity of e + 2n messages and message size of O(n), where n is the number of nodes, e is the number of edges and d is the diameter in the wait-for graph. The performance of the proposed algorithm is compared with that of the existing centralised algorithms in terms of deadlock duration, message traffic and message size using simulation. Numerical results reveal that the performance of the proposed algorithm is equal or better than that of the existing algorithms.