Multi-cycle Deadlock Detection Algorithm for Distributed Systems

Mohammad Ariful Islam; Md. Serajul Islam; Shifat Jahan

doi:10.18034/ajase.v5i1.72

Authors

Mohammad Ariful Islam Programmer, ICT Wing, Bangladesh Election Commission, Dhaka, BANGLADESH
Md. Serajul Islam Assistant Programmer, National ID Registration Wing, Bangladesh Election Commission, Dhaka, BANGLADESH
Shifat Jahan Assistant Programmer, National ID Registration Wing, Bangladesh Election Commission, Dhaka, BANGLADESH

Keywords:

Distributed system

deadlock

algorithm

deadlock algorithm

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.

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 DOI: https://doi.org/10.1007/978-3-540-75444-2_53

Chandy, K.M., Misra, J., Haas, L.M.: Distributed Deadlock Detection. ACM Transactionon Computer Systems. 144–156 (1983) DOI: https://doi.org/10.1145/357360.357365

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 DOI: https://doi.org/10.1145/800220.806693

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) DOI: https://doi.org/10.1109/32.21721

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. DOI: https://doi.org/10.1109/CIT.2005.69

Kashemkalyani, A.D., Singhal, M.: Invariant Based Verification of a Distributed Deadlock Detection Algorithm. IEEE Transactions on Software Engineering 17(8), 789–799 (1991) DOI: https://doi.org/10.1109/32.83914

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) DOI: https://doi.org/10.1109/TSE.1985.231844