- Wei Lu1,
- Yong Yang ORCID:orcid.org/0000-0002-0172-48901,
- Liqiang Wang2,
- Weiwei Xing1,
- Xiaoping Che1 &
- …
- Lei Chen1
1020Accesses
2Citations
Abstract
Deadlock detection in a distributed system without shared memory is important to ensure the reliability of the system. It becomes more complex when multiple deadlock detection algorithm instances execute concurrently in the system. In addition, the problem of communication disconnection between computing nodes or processes makes deadlock detection more difficult. Existing centralized algorithms suffer from single point failure of the central controller (due to communication disconnection), and they are performance-inefficient in the case of concurrent execution. In this paper, we extend our previous work (Lu et al.2016) and propose a fault tolerant deadlock detection algorithm in distributed systems. The extended proposed algorithm can tolerate a certain extent of communication disconnection between computing nodes or processes. A central controller is used to collect requesting conditions, construct a wait-for graph, and detect deadlocks. The proposed algorithm can select a new central controller if the current central leader fails due to communication disconnections. The liveness and safety properties of the proposed algorithm are proved in this paper. Experimental results show that the proposed algorithm provides better performance than most of existing algorithms in terms of message number, data traffic, and execution time. In addition, the proposed algorithm provides additional fault tolerance compared to existing deadlock detection algorithms in the case of communication disconnection.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.







Similar content being viewed by others
References
Agarwal, R., Bensalem, S., Farchi, E., Havelund, K., Nir-Buchbinder, Y., Stoller, S. D., Ur, S., & Wang, L. (2010). Detection of deadlock potentials in multi-threaded programs. IBMJournal of Research and Development, 54(5).
Agarwal, R, Wang, L, & Stoller, S. D. (2006). Detecting potential deadlocks with static analysis and runtime monitoring. InProceedings of the parallel and distributed systems, testing and debugging (Vol. 5503, pp. 425–439). Berlin: Springer.
Bracha, G, & Toueg, S (1987). Distributed deadlock detection.Distributed Computing, Springer Berlin Heidelberg,2(3), 127–138.
Brzezinski, J, Helary, J-M, Raynal, M, & Singhal, M (1995). Deadlock models and a general algorithm for distributed deadlock detection.Journal of Parallel and Distributed Computing Elsevier,31(2), 112–125.
Cidon, I., Jaffe, J., & Sidi, M. (1987). Distributed store-and-forward deadlock detection and resolution algorithms.IEEE Transactions on Communications IEEE,35 (11), 1139–1145.
Chen, S, Deng, Y, Attie, P, & Sun, W (1996). Optimal deadlock detection in distributed systems based on locally constructed wait-for graphs. InProceedings of the 16th international conference on distributed computing systems (pp. 613–619). IEEE.
Gupta, S (2013). Deadlock detection techniques in distributed database system.International Journal of Computer Applications, Foundation of Computer Science 74(21).
Ho Gary, S, & Ramamoorthy, CV (1982). Protocols for deadlock detection in distributed database systems.IEEE Transactions on Software Engineering IEEE,6, 554–557.
Holt, RC (1972). Some deadlock properties of computer systems.ACM Computing Surveys (CSUR) ACM,4(3), 179–196.
Huang, H, Wang, L, Lee, E-J, & Chen, P (2012). An MPI-CUDA implementation and optimization for parallel sparse equations and least squares (LSQR).Procedia Computer Science Elsevier,9, 76–85.
Knapp, E (1987). Deadlock detection in distributed databases.ACM Computing Surveys (CSUR) ACM,19(4), 303–328.
Kshemkalyani Ajay, D, & Mukesh, S (1994). Efficient detection and resolution of generalized distributed deadlocks.IEEE Transactions on Software Engineering IEEE,20(1), 43–54.
Kshemkalyani Ajay, D, & Mukesh, S (1997). Distributed detection of generalized deadlocks. InProceedings of the 17th international conference on distributed computing systems (pp. 553–560). IEEE.
Kshemkalyani Ajay, D, & Mukesh, S (1999). A one-phase algorithm to detect distributed deadlocks in replicated databases.IEEE Transactions on Knowledge and Data Engineering IEEE,11(6), 880–895.
Lee, S (2001). Efficient generalized deadlock detection and resolution in distributed systems. InThe 21st international conference on distributed computing systems (pp. 47–54). IEEE.
Lee, S (2004). Centralized detection and resolution of distributed deadlocks in the generalized model.IEEE Transactions on Software Engineering IEEE,30(9), 561–573.
Lu, W, Yang, Y, Wang, L, Xing, W, & Che, X (2015).A novel concurrent generalized deadlock detection algorithm in distributed systems, algorithms and architectures for parallel processing (pp. 479–493). Berlin: Springer.
Lu, W, Yang, Y, Wang, L, Xing, W, & Che, X (2016). A leader election based deadlock detection algorithm in distributed systems. InProceedings of the 1st international workshop on specification, comprehension, testing, and debugging of concurrent programs (pp. 12–19). ACM.
Luo, K. C. K., Klostermeyer, W. F., & Chow, Y. -C. (1993). A distributed algorithm for detecting and resolving store-and-forward deadlocks in networks with minimum exchange buffers. InINFOCOM ’93. Proceedings twelfth annual joint conference of the IEEE computer and communications societies (pp. 994–1003). IEEE.
Ma, H, Diersen, SR, Wang, L, Liao, C, Quinlan, D, & Yang, Z (2013). Symbolic analysis of concurrency errors in openmp programs. InThe 42nd international conference on parallel processing (pp. 510–516). IEEE.
Menasce, DA, & Muntz, RR (1979). Locking and deadlock detection in distributed data bases.IEEE Transactions on Software Engineering IEEE,3, 195–202.
Raynal, M (2014). Simple deadlock detection for the and-communication model. InEighth international conference on complex, intelligent and software intensive systems (CISIS ’14) (pp. 273–278). IEEE.
Selvaraj, S, & Ramasamy, R (2010). An efficient detection and resolution of generalized deadlocks in distributed systems.International Journal of Computer Applications,1(19), 1–7.
Singh, S, & Tyagi, SS (2012). A review of distributed deadlock detection techniques based on diffusion computation approach.International Journal of Computer Applications, Foundation of Computer Science,48(9), 28–32.
Srinivasan, S, & Rajaram, R (2011). A decentralized deadlock detection and resolution algorithm for generalized model in distributed systems.Distributed and Parallel Databases Springer Berlin Heidelberg,29(4), 261–276.
Srinivasan, S, & Rajaram, R (2012). An improved, centralised algorithm for detection and resolution of distributed deadlock in the generalised model.International Journal of Parallel, Emergent and Distributed Systems Taylor Francis,27(3), 205–224.
Tao, Z, Hui, L, Zhu, B, & Wang, Y (2014). A semi-centralized algorithm to detect and resolve distributed deadlocks in the generalized model. InIEEE 17th international conference on computational science and engineering (CSE ’14) (pp. 735–740). IEEE.
Tomar, P., & Bhardwaj, M. (2015). A review on deadlock detection in distributed database.Advances in Computer Science and Information Technology,2(8), 63–65.
Wang, L, Lu Shiyong, Xubo, F, Artem, C, Victoria, BH, & Ram, J (2009). Atomicity and provenance support for pipelined scientific workflows.Journal of Future Generation Computer Systems Elsevier,25(5), 568–576.
Acknowledgements
This work is supported in part by the National Natural Science Foundation of China (Nos. 61272353, 61370128, 61428201, and 61502028), the National Science Foundation of USA (No. 1622292), Program for New Century Excellent Talents in University (NCET-13-0659), Beijing Higher Education Young Elite Teacher Project (YETP-0583).
Author information
Authors and Affiliations
School of Software Engineering, Beijing Jiaotong University, Beijing, 100044, China
Wei Lu, Yong Yang, Weiwei Xing, Xiaoping Che & Lei Chen
Department of Computer Science, University of Central Florida, Orlando, FL, 32816, USA
Liqiang Wang
- Wei Lu
You can also search for this author inPubMed Google Scholar
- Yong Yang
You can also search for this author inPubMed Google Scholar
- Liqiang Wang
You can also search for this author inPubMed Google Scholar
- Weiwei Xing
You can also search for this author inPubMed Google Scholar
- Xiaoping Che
You can also search for this author inPubMed Google Scholar
- Lei Chen
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toYong Yang.
Rights and permissions
About this article
Cite this article
Lu, W., Yang, Y., Wang, L.et al. A fault tolerant election-based deadlock detection algorithm in distributed systems.Software Qual J26, 991–1013 (2018). https://doi.org/10.1007/s11219-017-9379-1
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative