| Abstract: | Numerous edge-chasing deadlock detection algorithms were developed for the cycle detection in distributed systems, but their detections had the n steps speed limitation and n(n-1) overhead limitation to detect a cycle of size n under the one-resource request model. Since fast deadlock detection is critical, this paper proposed a new algorithm to speed up the detection process. In our algorithm, when the running of a transaction node is blocked, the being requested resource nodes reply it with the waiting or being waited message simultaneously, so the blocked node knows both its predecessors and successors, which helps it detecting a cycle of size 2 directly and locally. For the cycle of size n (n＞2), a special probe is produced which has the predecessors information of its originator, so the being detected nodes know their indirect predecessors and direct successors, and can detect the cycle within n-2 steps. The proposed algorithm is formally proved to be correct by the invariant verification method. Performance evaluation shows that the message overhead of our detection is (n2-n-2)/2, hence both the detection speed and message cost of the proposed algorithm are better than that of the existing algorithms. |
