A Review Paper on Deadlock Detection in Distributed System

Issue: Vol.9 No.1

Authors:

Palak Arora (Manav Rachna International University, Faridabad)

Keywords: Database, Distributed database, Deadlock, Deadlock detection

Abstract:

If we don’t have the distributed shared memory then the systems are easily prone to deadlocks. Deadlock is basically the result of uncontrolled sequence of request and release of resources among a number of different processes in distributed system. This survey paper presents some of the system models like and , or , unrestricted etc. and some selected deadlock detection algorithms like Chandy and Mishra ,  Obermarck etc. are also presented to see how in deadlocks are detected in different types of algorithms.

Download PDF

References:

[1] Chandy, K.M., Misra, J., and Haas, L. M. 1983. Distributed deadlock detection. ACM Trans. Comput. Syst. 1,2 (May), 144-156.

[2] R. Obermarck. “Distributed deadlock detection algorithm,” ACM Trans. Database SW., vol. 7, pp. 187-208. June 1982. M

[3] B. M. M. Alom, F. Henskens, and M. Hannaford, “Deadlock Detection Views of Distributed Database,” in
International conference on Information Technology & New Generation (ITNG-2009) Las Vegas, USA: IEEE Computer Society, 2009.

[4] G. S. Ho and C. V. Ramamoorthy, “Protocols for Deadlock Detection in Distributed Database Systems” IEEE Transaction on Software Engineering, vol. 8:6, pp. 554-557, 1982.

[5] Elmagarmid A. K. A Survey of Distributed Deadlock Detection Algorithms, SIGMOD RECORD, Vol. 15, No.3, pp. 37-45, 1986.

[6] Mukesh Singhal “Deadlock Detection In Distributed Systems”, November 1989.

[7] D.P Mitchell and M.J. Merrit, “A Distributed Algorithm For Deadlock Detection and Resolution” Proc ACM Conf. Aug 1984.

[8] Bracha, G., and Toueg, S. 1983. A distributed algorithm for generalized deadlock detection. Tech. Rep. TR 83-558, Cornell Univ., Ithaca, N.Y. BRACHA, G., AND TOUEG, S. 1984. A distributed algorithm for generalized deadlock detection. In Proceedings of the ACM Symposium on Principles of Distributed Computing (Vancouver, Canada, Aug.). ACM, New York, pp. 285-301.

[9] Chandy, K.M., and Lamport, L. 1985. Distributed snapshots: Determining global states of distributed
systems. ACM Trans. Program. Lang. Syst. 3, 1 (Feb.), 63-75.

[10] Chandy, K.M., and Misra, J. Distributed computation on graphs: Shortest path algorithms. Commun. ACM 25, 11 (Nov. 1982), 833-837.

[11] Edgar Knapp, “Deadlock Detection In Distributed Database Systems” ACM Computing surveys, Dec. 1987.

[12] Ajay Kshemkalyani and Mukesh Singhal, “Distributed Computing: Principles, Algorithms, and Systems” ACM Computing Machines, 2008.

[13] Prabhsimran Singh, Sukhmanjit Kaur and Neha Bassan, “Approaches for Deadlock Detection for Distributed Systems”, Dec. 2015.

[14] Alom B.M. Monjurul, Frans Alexander Henskens, Michael Richard Hannaford, “Deadlock Detection  Views of Distributed Database”, IEEE Sixth International Conference on Information Technology: New Generations, Page(s):730–737, 2010.

[15] Kshemkalyani, A. D., and Singhal, M., “Efficient Detection and Resolution of Generalized Distributed Deadlocks,” IEEE Trans. on Software Engineering, January 1994.

[16] Singhal, M., “Deadlock Detection in Distributed Systems,” IEEE Computer, November 1989.