Abstract
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 language | English |
---|---|
Pages (from-to) | 852-870 |
Number of pages | 19 |
Journal | International Journal of Communication Systems |
Volume | 27 |
Issue number | 6 |
DOIs | |
Publication status | Published - 2014 Jun |
Keywords
- cloud computing
- deadlock detection
- gossip protocol
- unstructured algorithm
ASJC Scopus subject areas
- Electrical and Electronic Engineering
- Computer Networks and Communications