Deadlock Detection Techniques in Distributed Database System

Authors:

Swati Gupta (Amity University, Gurgoan)

Suresh Kumar (Manav Rachna International University)

Keywords: Wait-For-Graph, Deadlock, Local Transaction Structure.

Abstract:

Distributed database system provides resource sharing environment for optimal performance of various database activities, especially when data is spread over a large number of sites. Distributed nature of transactions occurring at different sites and requiring resources from diverse sites pose various operational problems, such as deadlocks, concurrency and data recovery. A deadlock may occur when a transaction enters into wait state which request resource from other blocked transactions. The deadlocks are handled in three phases namely deadlock detection, deadlock avoidance and deadlock detection. Various algorithms have been discussed in the literature for deadlock detection and resolution. These algorithms quite often fail to detect deadlock over distributed database. In this paper an attempt has been made to develop an algorithm for distributed deadlock detection at local and global levels. We have developed local transaction structure to deal with deadlock at local level and distributed transaction structure at global level.

References:

1. Alom B.M. Monjurul, Frans Alexander Henskens, Michael Richard Hannaford, Optimization of Detected Deadlock Views of Distributed Database, International Conference on Data Storage and Data Engineering , pp. 44-48, ISBN: 978-0- 7695-3958-4, 2010.

2. Carlos F. Alastruey, Federico Fariña, Jose Ramon Gonzalez de Mendivil, “A Distributed Deadlock Resolution Algorithm for the AND Model”, IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 5, pp. 433-447, May 1999.

3. Chandy K. M., Hass L. M and Misra J, “Distributed Deadlock Detection”, ACM Transactions on Computer Systems, vol. 1, no. 2, pp. 144-56, 1983.

4. Elmagarmid A. K., “A Survey of Distributed Deadlock Detection Algorithms”, SIGMOD RECORD, vol. 15, no. 3, pp. 37-45, 1986.

5. Gray J., “A Straw Man Analysis of the Probability of Waiting and Deadlocks in Database Systems”, IBM Research Report, 1981.

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

7. Mehdi Hashemzadeh, Nacer Farajzadeh, Abolfazl T. Haghighat, “Optimal Detection and Resolution of Distributed Deadlocks in the Generalized Model,” 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP’06), pp.133-136, 2006.

8. Menasce D. A. and Muntz R. R., “Locking and Deadlock Detection in Distributed Data Bases”, IEEE Transaction on Software Engineering, vol. 5, no.3, pp. 195-202, 1979.

9. Merritt M. J. and Mitchell D. P., “A Distributed Algorithm for Deadlock Detection and Resolution,” ACM Transactions, vol. 2, no. 3, pp. 95-99, 1984.

10. Singhal Mukesh “Deadlock Detection in Distributed System” IEEE Transaction on Software Engineering, vol. 4, no. 3, pp. 195-199, 1989.

11. Jain Kamal, MohammadTaghi Hajiaghayi and Kunal Talwar, “The Generalized Deadlock Resolution Problem”, Autoomata Languages and Programming, Lecture Notes in Computer Science, 2005, vol. 3580/2005, 103, DOI: 10.1007/ 11523468_69

12. Nacer Farajzadeh, Mehdi Hashemzadeh, Morteza Mousakhani, Abolfazl T. Haghighat, “An Efficient Generalized Deadlock Detection and Resolution Algorithm in Distributed Systems”, Fifth International Conference on Computer and Information Technology (CIT’05), pp. 303-309, 2005.

13. Qinqin Ni, Weizhen Sun and Sen Ma, “Deadlock Detection Based on Resource Allocation Graph”, Fifth International Conference on Information Assurance and Security, vol. 2, pp.135-138, 2009.

14. Selvaraj S. and R. Rajaram, “A Decentralized Deadlock Detection and Resolution Algorithm for Generalized Model in Distributed Systems”, Journal of Distributed and Parallel Databases, vol. 29, No. 4, pp. 261-276, DOI: 10.1007/s10619- 011-7078-7

15. Soojung L. and Junguk L. Kim, “Performance Analysis of Distributed Deadlock Detection Algorithms”, IEEE Transactions in Knowledge and Data Engineering, vol. 13, no. 4, pp. 623-636, August 2001.

16. T. Ozsu and Valduriez P., “Principle of Distributed Database Systems”, Prentice Hall, 1999