Premium
Unstructured deadlock detection technique with scalability and complexity‐efficiency in clouds
Author(s) -
Lim JongBeom,
Suh Taeweon,
Yu Heonchang
Publication year - 2014
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.2638
Subject(s) - computer science , deadlock prevention algorithms , scalability , liveness , gossip , correctness , distributed computing , deadlock , fault tolerance , gossip protocol , protocol (science) , algorithm , medicine , psychology , social psychology , alternative medicine , pathology , database
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.