A Novel Concurrent Generalized Deadlock Detection Algorithm In Distributed Systems

Keywords

Concurrent coordination; Deadlock detection; Distributed system; False negative

Abstract

Detecting deadlocks has been considered an important problem in distributed systems. Many approaches are proposed to handle this issue; however, little attention has been paid on coordinating concurrent execution of distributed deadlock detection algorithms. Previous approaches may report incorrect results (false negatives), and they are inefficient due to lack of proper coordination of concurrent execution. In this paper, we present a novel concurrent coordination algorithm for distributed generalized deadlock detection. The proposed algorithm aims to avoid false negatives and improve the performance when concurrently executing deadlock detection in a distributed system. Our algorithm adopts diffusion computation to distribute probe messages and employs priority-based method to coordinate concurrent algorithm instances. Priority carried in the received probe messages will be locally recorded by each initiator. Instead of being suspended by higher priority algorithm instances, lower priority algorithm instances can accomplish deadlock detection locally. The initiator with the highest priority will receive and collect all related resource requests information from lower priority instances in a hierarchical manner and perform global deadlock detection at last. We evaluate our algorithm on a bunch of event-driven simulations. The experimental results show that our approach can achieve better accuracy and efficiency compared to previous approaches.

Publication Date

1-1-2015

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

9529

Number of Pages

479-493

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/978-3-319-27122-4_33

Socpus ID

84951955623 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84951955623

This document is currently not available here.

Share

COinS