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 Jan 1

    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