A fault tolerant election-based deadlock detection algorithm in distributed systems

摘要

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.