This work introduces a new distributed history-based algorithm for deadlock detection and resolution under the single-unit request model. The algorithm has a communiation cost of O( n ? 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 confict 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 an switch to a higher level depending on the information received in the probes.