A Fault Tolerant Election-Based Deadlock Detection Algorithm In Distributed Systems

Keywords

Deadlock detection; Distributed system; Fault tolerance; Generalized deadlock; Leader election

Abstract

Deadlock detection in a distributed system without shared memory is important to ensure the reliability of the system. It becomes more complex when multiple deadlock detection algorithm instances execute concurrently in the system. In addition, the problem of communication disconnection between computing nodes or processes makes deadlock detection more difficult. Existing centralized algorithms suffer from single point failure of the central controller (due to communication disconnection), and they are performance-inefficient in the case of concurrent execution. In this paper, we extend our previous work (Lu et al. 2016) and propose a fault tolerant deadlock detection algorithm in distributed systems. The extended proposed algorithm can tolerate a certain extent of communication disconnection between computing nodes or processes. A central controller is used to collect requesting conditions, construct a wait-for graph, and detect deadlocks. The proposed algorithm can select a new central controller if the current central leader fails due to communication disconnections. The liveness and safety properties of the proposed algorithm are proved in this paper. Experimental results show that the proposed algorithm provides better performance than most of existing algorithms in terms of message number, data traffic, and execution time. In addition, the proposed algorithm provides additional fault tolerance compared to existing deadlock detection algorithms in the case of communication disconnection.

Publication Date

9-1-2018

Publication Title

Software Quality Journal

Volume

26

Issue

3

Number of Pages

991-1013

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s11219-017-9379-1

Socpus ID

85020537334 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS