An O(n) distributed deadlock resolution algorithm

This paper shows a new distributed algorithm for dead-lock detection and resolution under the single-resource re-quest model that highly improves the complexity measure-ments of previous proposals. The algorithm has a commu-nication cost of 2n−1 messages and a latency of n ·T for a deadlock cycle of n processes, where T is the inter-site com-munication delay. The algorithm achieves this improvement even verifying the strongest correctness criteria considered in previous works: it resolves all deadlocks in finite time and does not resolve false deadlocks