A distributed deadlock detection algorithm for mobile computing system

The mode of mobile computing originated from distributed computing and it has the un-idempotent operation property, therefore the deadlock detection algorithm designed for mobile computing systems will face challenges with regard to correctness and high efficiency. This paper attempts a fundamental study of deadlock detection for the AND model of mobile computing systems. First, the existing deadlock detection algorithms for distributed systems are classified into the resource node dependent (RD) and the resource node independent (RI) categories, and their corresponding weaknesses are discussed. Afterwards a new RI algorithm based on the AND model of mobile computing system is presented. The novelties of our algorithm are that: 1) the blocked nodes inform their predecessors and successors simultaneously; 2) the detection messages (agents) hold the predecessors information of their originator; 3) no agent is stored midway. Additionally, the quit-inform scheme is introduced to treat the excessive victim quitting problem raised by the overlapped cycles. By these methods the proposed algorithm can detect a cycle of size n within n-2 steps and with (n^2-n-2)/2 agents. The performance of our algorithm is compared with the most competitive RD and RI algorithms for distributed systems on a mobile agent simulation platform. Experiment results point out that our algorithm outperforms the two algorithms under the vast majority of resource configurations and concurrent workloads. The correctness of the proposed algorithm is formally proven by the invariant verification technique.