Research On Deadlock Detection Algorithm In Distributed Database

Deadlock detection in distributed database is an important problem in the area of concurrency control. In the research area of distributed systems, deadlock conditions are commonly determined by resource request mode.According to different resource request that issued by transactions, existing deadlock detection algorithms of distributed database are commonly presented for certain resource request model. Distributed database is different from general distributed system, it's deadlock condition is not only related with resource request mode, but also related with resource grant mode. Moreover, because existing deadlock detection algorithms of distributed database commonly adopt X lock mode or S/X lock mode, and lose sight of multiple lock mode which is applied widely in distributed database systems, these algorithms can not be applied availably in distributed database systems. In this paper, distirbuted transaction, concurrency control and resource request model are introduced in detail. The universal deadlock condition in distirbuted database system is summarized. Deadlock detection algorithms of distributed database can be classified into centralized, layered and distributed. Centralized and layered algorithms commonly have higer correctness, but their number of messages are too great. By contraries, for distributed algorithms, their number of messages are commonly petty, but their correctness is poor. Because distirbuted algorithms are more agile and efficient, this paper will lucubrate disitributed deadlock detection algorithms and bring forward a new distributed algorithm—an deadlock detection algorithm based DDA and modifyed probe. This algorithm combinate the ideal of the global state detection method (DDA algorithm) and algorithms based on probe. It presents a new rule of probe transmission, that is when transaction node receives the first probe (contains initial probe), the node will accept and record the probe, when transaction node receives other probe again, the node refuse the probe(stop the probe transmission) and record the probe-couple(refused probe,accepted probe). In this algorithm, the notations of Probe-Couple, Extented-Probe and Probe-Cluster.etc are given, and a new mechanism of deadlock detection is built, if there is a probe-path{(Xi,Yi)}(1<=i<=n),and Ynis the base of X1,then there is a cycle in WFG. This algorithm can reduce the number of global information transmission by using merge computation of the probe-couple. So this algorithm can avoid false deadlock and phantom deadlock, can avoid undetected deadlock, reduce the number of messages.Finally, the correctness and performance of this algorithm are analysed, and tested by simulation experimentation.