A semi-centralized algorithm using adaptive gossip to detect and resolve distributed deadlocks

摘要

Distributed deadlock detection is a very complex task as no node has correct and complete information about the overall state of the system. An adaptive gossip based semi-centralized deadlock detection algorithm is proposed in this paper. Due to the basic inherent nature of the gossip protocol, our distributed deadlock detection algorithm using adaptive gossip can be said to be fault-tolerant, scalable and efficient while maintaining correctness properties - liveness and safety. Performance analysis of our algorithm shows that it performs well in terms of both time and message complexity.