Unstructured deadlock detection technique with scalability and complexity‐efficiency in clouds
JongBeom Lim, Taeweon Suh, Heonchang Yu · International Journal of Communication Systems · 2013
SUMMARY 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. Copyright © 2013 John Wiley & Sons, Ltd.