TY - JOUR
T1 - Unstructured deadlock detection technique with scalability and complexity-efficiency in clouds
AU - Lim, Jongbeom
AU - Suh, Taeweon
AU - Yu, Heonchang
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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.
AB - 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.
KW - cloud computing
KW - deadlock detection
KW - gossip protocol
KW - unstructured algorithm
UR - http://www.scopus.com/inward/record.url?scp=84902509709&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902509709&partnerID=8YFLogxK
U2 - 10.1002/dac.2638
DO - 10.1002/dac.2638
M3 - Article
AN - SCOPUS:84902509709
SN - 1074-5351
VL - 27
SP - 852
EP - 870
JO - International Journal of Communication Systems
JF - International Journal of Communication Systems
IS - 6
ER -