一种快速低开销的分布式死锁检测解决算法

Fast and Low Cost Deadlock Detection and Resolution in Distributed Systems

现有的分布式edge-chasing死锁检测算法具有消息开销大或不能并发执行的弱点,为此提出一个新的死锁检测算法,算法中检测消息由事务节点发起并在事务节点和资源节点之间传递,不保留死锁检测的中间状态,也不更新事务的资源访问请求。算法的正确性得到证明,仿真表明新算法的时间和消息开销低于同类算法。

Previous proposals of distributed deadlock detection algorithms remain the disadvantages of high overhead and unconcurrency. This paper proposes an efficient “ edge chasing” algorithm to eliminate these problems, in where probes are created and propagated by both transaction and data sites. The proposed algorithm neither keeps temporary detection states nor resends resource requests for a transaction, so it speeds up the deadlock detection process, decreases the detection overhead and executes concurrendy. The solution is proved correctness, performance simulation shows its detection overhead and timing are better than existing algorithms.