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

Jongbeom Lim, Taeweon Suh, Heonchang Yu

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)852-870
Number of pages19
JournalInternational Journal of Communication Systems
Issue number6
Publication statusPublished - 2014 Jun


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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Networks and Communications


Dive into the research topics of 'Unstructured deadlock detection technique with scalability and complexity-efficiency in clouds'. Together they form a unique fingerprint.

Cite this