Cost of distributed deadlock detection: a performance study

A performance evaluation of two classes of distributed deadlock detection algorithms, namely, set-based and probe-based distributed deadlock detection algorithms, is presented. The performance evaluation is performed on a simulated distributed database by implementing the algorithms. The performance evaluation shows two main results. First, set-based algorithms outperform probe-based algorithms. Second, current analytical models of distributed deadlock detection are very optimistic because they only compute the overhead of deadlock detection when deadlock exists. It is shown that this overhead cost is only a small portion of the total overall cost, that is, the cost of running the algorithm when deadlock does not exist dominates the cost of the algorithm when deadlock does exist