Multi-cycle Deadlock Detection Algorithm for Distributed Systems
Keywords:
Abstract
Deadlock handling is an important component of transaction management in a database system. Though a lot of works have already done for deadlock detection on distributed system. This paper proposes a multi-cycle deadlock detection and recovery mechanism. Our proposed algorithm has modified the probe based distributed algorithm for deadlock detection such as CMH algorithm. But CMH algorithm had some limitation. It can only detect single cycle. But some situation a node is responsible for multi-cycle deadlock detection. In this situation, it can’t detect Multi-cycle deadlock. Besides it can only detect deadlock when the initiator node involved in the cycle. Another algorithm named MC2DR has worked on CMH algorithm. But their probe message contains four fields for deadlock detection which takes more space, but our algorithm has reduced the MC2DR algorithm probe message field and increased the efficiency of this algorithm. It can detect multi-cycle and also detect which node is responsible for multi-cycle deadlock and kills it.
Downloads
References
Abdur Razzaque. Md., Mamun-Or-Rashid. Md., Ch.Hong, “MC2DR: Multi-cycle Deadlock Detection and Recovery Algorithm for Distributed Systems", LNCS 4782(HPCC2007), Sep 26- 28 2007, pp. 554-565
Chandy, K.M., Misra, J., Haas, L.M.: Distributed Deadlock Detection. ACM Transactionon Computer Systems. 144–156 (1983)
Chandy, K.M., Misra, J.: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. In: Proceedings of the ACM Symposium on Principles of DistributedComputing, Ottawa, Canada, pp. 157–164. ACM Press, New York (1982) MC2DR: Multi-cycle Deadlock Detection and Recovery Algorithm 565
Choudhary, A.N., Kohler, W.H., Stankovic, J.A., Towsley, D.: A Modified PriorityBased Probe Algorithm for Distributed Deadlock Detection and Resolution. IEEETransactions on Software Engg. 15(1), 10–17 (1989)
Farajzadeh. N, Hashemzadeh. M, Mousakhani. M, Haghighat, .A,"An Efficient Generalized Deadlock Detection and Resolution Algorithm in Distributed Systems", In: Proc.5th IEEE Int'l Conf. Computer and Information Technology (CIT'05), 2005.
Kashemkalyani, A.D., Singhal, M.: Invariant Based Verification of a Distributed Deadlock Detection Algorithm. IEEE Transactions on Software Engineering 17(8), 789–799 (1991)
Kim, Y.M., Lai, T.W., Soundarajan, N.: Efficient Distributed Deadlock Detectionand Resolution Using Probes, Tokens, and Barriers. In: Proc. Int’l Conf. on Paralleland Distributed Systems, pp. 584–591 (1997)
Lee, S., Kim, J.L.: An Efficient Distributed Deadlock Detection Algorithm. In: Proc.15th IEEE Int’l Conf. Distributed Computing Systems, pp. 169–178 (1995)
Lee, S.: Fast Detection and Resolution of Generalized Distributed Deadlocks. In: EUROMICRO-PDP 2002 (2002)
Sinha, M.K., Natarajan, N.: A Priority Based Distributed Deadlock Detection Algorithm.IEEE Trans. Software Engg. 11(1), 67–80 (1985)
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2016 Asian Journal of Applied Science and Engineering
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.