A low communication cost algorithm for distributed deadlock detection and resolution

This work introduces a new distributed history-based algorithm for deadlock detection and resolution under the single-unit request model. The algorithm has a communication cost of O(n /spl middot/ log n) messages for a deadlock cycle of n processes. This low cost is achieved by means of two mechanisms. On one hand, to reduce the number of instance initializations, a node compares the priorities between its immediate successor and all its predecessors, starting the algorithm only if an antagonistic conflict is given. On the other hand, each instance of the algorithm runs at a certain detection level and does not retransmit probes created by instances running at a lower detection level. An instance can switch to a higher level depending on the information received in the probes.