Unstructured deadlock detection technique with scalability and complexity-efficiency in clouds

作者：Lim JongBeom; Suh Taeweon; Yu Heonchang^*

来源：International Journal of Communication Systems, 2014, 27(6): 852-870.

DOI：10.1002/dac.2638

• deadlock detection
• unstructured algorithm
• gossip protocol
• cloud computing

To detect deadlock in distributed systems, the initiator should construct an efficient explicit or implicit global wait-for graph. In this paper, we present an unstructured deadlock detection algorithm using a gossip protocol in cloud computing environments, where constituting nodes may join and leave at any time. Because of the inherit properties of a gossip protocol, we argue that our proposed deadlock detection algorithm is scalable, fault-tolerant, and efficient, retaining safety and liveness properties. The correctness proof of the algorithm is also provided. The message complexity of our proposed algorithm is O(n), where n is the number of nodes. Our performance evaluation with scalable settings shows that our approach has a significant advantage over previous deadlock detection algorithms in terms of solving scalability, fault-tolerance, and complexity-efficiency issues.

• 出版日期2014-6