A new distributed deadlock detection algorithm for distributed database systems

A new distributed deadlock detection algorithm is proposed. Deadlock is detected through passing special messages, called probes, along the edges of the wait-for graphs in the system. The algorithm is an improved version of Chandy´s algorithm (M. Chandy and J. Misra, 1982) which fails completely in certain cases. The new algorithm has been tested through extensive simulation experiments. Besides being error free, it is shown to suffer very little performance degradation from the additional deadlock detection overhead in comparison to the original algorithm. The algorithm has also compared with time-out method. It is found that for large values of multiprogramming level, the probe based algorithm can outperform time-out. The performance results indicate that in the modified algorithm, the rate of probe initiation is a dominant factor in determining system performance