Daemon- Based Distributed Deadlock Detection and Resolution
detecting the deadlock is one of the important
problems in distributed systems and different solutions have been
proposed for it. Among the many deadlock detection algorithms,
Edge-chasing has been the most widely used. In Edge-chasing
algorithm, a special message called probe is made and sent along
dependency edges. When the initiator of a probe receives the probe
back the existence of a deadlock is revealed. But these algorithms are
not problem-free. One of the problems associated with them is that
they cannot detect some deadlocks and they even identify false
deadlocks. A key point not mentioned in the literature is that when
the process is waiting to obtain the required resources and its
execution has been blocked, how it can actually respond to probe
messages in the system. Also the question of 'which process should
be victimized in order to achieve a better performance when multiple
cycles exist within one single process in the system' has received
little attention. In this paper, one of the basic concepts of the
operating system - daemon - will be used to solve the problems
mentioned. The proposed Algorithm becomes engaged in sending
probe messages to the mandatory daemons and collects enough
information to effectively identify and resolve multi-cycle deadlocks
in distributed systems.
[1] 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
[2] Chandy, KM, Misra, J,"A distributed algorithm for detecting resource
deadlocks in distributed systems". In Proc. ACM SIGA CT-SIGOPS
Syrup, 1982, pp. 157-164
[3] Chandy KM, Misra .J, Haas LM, "Distributed Deadlock Detection",
ACM Transactions on Computer Systems, May 1983,Vol 1,No. 2.PP
144-156
[4] Choudhary et al," A Modified Priority Based Probe Algorithm for
Distributed Deadlock Detection and Resolution", IEEE Trans Software,
January 1989, vol.15, No.1, pp .10-17
[5] 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.
[6] Knapp, E, "Deadlock Detection in Distributed Databases". ACM
Computing Surveys, Dec.1988, vol.3, no. 4, pp.303-328.
[7] Kshemkalyani AD, Singhal M ,"Distributed detection of generalized
deadlocks". In: Proceedings of the 17th International Conference on
Distributed Computing System, IEEE Computer Society Press, 1997, pp
553-560
[8] Kshemkalyani, A. D, Singhal, M, "Invariant based verification of a
distributed deadlock detection algorithm," IEEE Trans. Software Eng,
Aug. 1991, vol 17, pp. 789-799.
[9] Lee.S,"Fast, Centralized Detection and Resolution of Distributed
Deadlocks in the Generalized Model", IEEE Transaction on Software
Engineering, September 2004, Vol. 30 , No.9 ,pp. 561-573
[10] Lee, S., Kim, JL,"An Efficient Distributed Deadlock Detection
Algorithm". In: Proc. 15th IEEE Int'l Conf. Distributed Computing
Systems, pp. 169-178 (1995)
[11] DP Mitchell and MJ Merritt,"A Distributed Algorithm for Deadlock
Detection and Resolution", Proc. Third ACM Symp. Principles of
Distributed Computing, pp. 282-284, Vancouver, Canada, Aug. 1984.
[12] MK Sinha and N. Natarjan, "A priority-based distributed deadlock
detection algorithm", IEEE Trans. Software Eng., Vol. SE-11, No. 1,
Jan. 1985, 67-80.
[13] Singhal, M, "Deadlock Detection in Distributed Systems", IEEE
Computer, Nov.1989, No 22, pp. 37-48.
[14] Tanenbaum ,A."Modern Operation Systems", 3 e, (c) Prentice-Hall, Inc.
2008
[1] 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
[2] Chandy, KM, Misra, J,"A distributed algorithm for detecting resource
deadlocks in distributed systems". In Proc. ACM SIGA CT-SIGOPS
Syrup, 1982, pp. 157-164
[3] Chandy KM, Misra .J, Haas LM, "Distributed Deadlock Detection",
ACM Transactions on Computer Systems, May 1983,Vol 1,No. 2.PP
144-156
[4] Choudhary et al," A Modified Priority Based Probe Algorithm for
Distributed Deadlock Detection and Resolution", IEEE Trans Software,
January 1989, vol.15, No.1, pp .10-17
[5] 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.
[6] Knapp, E, "Deadlock Detection in Distributed Databases". ACM
Computing Surveys, Dec.1988, vol.3, no. 4, pp.303-328.
[7] Kshemkalyani AD, Singhal M ,"Distributed detection of generalized
deadlocks". In: Proceedings of the 17th International Conference on
Distributed Computing System, IEEE Computer Society Press, 1997, pp
553-560
[8] Kshemkalyani, A. D, Singhal, M, "Invariant based verification of a
distributed deadlock detection algorithm," IEEE Trans. Software Eng,
Aug. 1991, vol 17, pp. 789-799.
[9] Lee.S,"Fast, Centralized Detection and Resolution of Distributed
Deadlocks in the Generalized Model", IEEE Transaction on Software
Engineering, September 2004, Vol. 30 , No.9 ,pp. 561-573
[10] Lee, S., Kim, JL,"An Efficient Distributed Deadlock Detection
Algorithm". In: Proc. 15th IEEE Int'l Conf. Distributed Computing
Systems, pp. 169-178 (1995)
[11] DP Mitchell and MJ Merritt,"A Distributed Algorithm for Deadlock
Detection and Resolution", Proc. Third ACM Symp. Principles of
Distributed Computing, pp. 282-284, Vancouver, Canada, Aug. 1984.
[12] MK Sinha and N. Natarjan, "A priority-based distributed deadlock
detection algorithm", IEEE Trans. Software Eng., Vol. SE-11, No. 1,
Jan. 1985, 67-80.
[13] Singhal, M, "Deadlock Detection in Distributed Systems", IEEE
Computer, Nov.1989, No 22, pp. 37-48.
[14] Tanenbaum ,A."Modern Operation Systems", 3 e, (c) Prentice-Hall, Inc.
2008
@article{"International Journal of Electrical, Electronic and Communication Sciences:59975", author = "Z. RahimAlipour and A. T. Haghighat", title = "Daemon- Based Distributed Deadlock Detection and Resolution", abstract = "detecting the deadlock is one of the important
problems in distributed systems and different solutions have been
proposed for it. Among the many deadlock detection algorithms,
Edge-chasing has been the most widely used. In Edge-chasing
algorithm, a special message called probe is made and sent along
dependency edges. When the initiator of a probe receives the probe
back the existence of a deadlock is revealed. But these algorithms are
not problem-free. One of the problems associated with them is that
they cannot detect some deadlocks and they even identify false
deadlocks. A key point not mentioned in the literature is that when
the process is waiting to obtain the required resources and its
execution has been blocked, how it can actually respond to probe
messages in the system. Also the question of 'which process should
be victimized in order to achieve a better performance when multiple
cycles exist within one single process in the system' has received
little attention. In this paper, one of the basic concepts of the
operating system - daemon - will be used to solve the problems
mentioned. The proposed Algorithm becomes engaged in sending
probe messages to the mandatory daemons and collects enough
information to effectively identify and resolve multi-cycle deadlocks
in distributed systems.", keywords = "Distributed system, distributed deadlock detectionand resolution, daemon, false deadlock.", volume = "4", number = "3", pages = "596-6", }