哈尔滨工业大学学报（英文版）2005，Vol.12Issue(5)：521-527,7.
A distributed deadlock detection algorithm for mobile computing system
A distributed deadlock detection algorithm for mobile computing system
摘要
Abstract
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 ( n2 - 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.关键词
mobile computing system/deadlock detection/AND model/cycle overlapKey words
mobile computing system/deadlock detection/AND model/cycle overlap分类
信息技术与安全科学引用本文复制引用
CHENG Xin,LIU Hong-wei ,ZUO De-cheng ,JIN Feng ,YANG Xiao-zong..A distributed deadlock detection algorithm for mobile computing system[J].哈尔滨工业大学学报（英文版）,2005,12(5):521-527,7.基金项目
Sponsored by the National 863 Plan (Grant No. 2002AAlZ2101 ) （Grant No. 2002AAlZ2101 ）
the National Tenth Five-Year Research Plan( Grant No. 41316. 1.2 ). （ Grant No. 41316. 1.2 ）
