Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Dynamic deadlock detection under the OR requirement model
Keywords:
Distributed systems, deadlock detection, deadlock resolution, self-stabilization, wait for graph, knotAbstract
Deadlock detection is one of the most discussed problems in the literature. Although several al- gorithms have been proposed, the problem is still open. In general, the correct operation of an algorithm depends on the requirement model being considered. This article introduces a deadlock detection algorithm for the OR model. The algorithm is complete, because it detects all deadlocks, and it is correct, because it does not detect false deadlocks. In addition, the algorithm supports dynamic changes in the wait-for graph on which it works. Once finalized the algorithm, at least each process that causes deadlock knows that it is deadlocked. Using this property, possible extensions are suggested in order to resolve deadlocks.
Downloads
Download data is not yet available.
References
[1] Gabriel Bracha and Sam Toueg. A distributed algorithm for generalized deadlock detection. In Symposium on Principles of Distributed Computing, pages 285-301, Vancouver, British Columbia, Canada, August 1984.
[2] K. Mani Chandy, Jayadev Misra, and Laura M. Haas. Distributed deadlock detection. ACM Transactions on Computer Systems, 1(2):144-156, May 1983
[3] Edsger Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643-644, November 1974.
[4] Mitchell Flatebo and Ajoy Kumar Datta. Self-stabilizing deadlock detection algorithms. In Proceedings of the1992 ACM Annual Conference on Communications, pages 117-122, Kansas City, Missouri, April 1992.
[5] Sukumar Ghosh and Arobinda Gupta. An exercise in fault-containment: self-stabilizing leader election. Information Processing Letters, 59(5):281{288, September 1996.
[6] José R. González de Mendívil, Federico Farina, José R. Garitagoitia, C. F. Alastruey , and J. M. Bernabeu-Auban. A distributed deadlock resolution algorithm for the AND model. IEEE Transactions on Parallel and Distributed Systems, 10(5):433{447, May 1999.
[7] T. Herman and K. Chandy. A distributed procedure to detect AND/OR deadlock. Technical Report TRLCS-8301, Department of Computer Science, University of Texas, Austin, Texas, 1983.
[8] Richard C.Holt. Some deadlock properties on computer systems. ACM Computing Surveys, 4(3):179-196, September 1972.
[9] Mehmet H. Karaata and Jeffery C. Line. Self-stabilizing algorithms for deadlock detection and identification in distributed systems. In Proceedings of the ISCA Thirteenth International Conference on Parallel and Distributed Computing, pages 320-325, Las Vegas, Nevada, August 2000.
[10] Edgar Knapp. Deadlock detection in distributed databases. ACM Computing Surveys, 19(4):303{328, December 1987.
[11] N. Natarajan. A distributed scheme for detecting communication deadlocks.IEEE Transactions on Software Engineering, SE- 12(4):531{537, April 1986.
[12] Marco Schneider. Self-stabilization. ACM Computing Surveys, 25(1):45{67, March 1993.
[13] Loren Schwiebert. Deadlock-free oblivious wormhole routing with cyclic dependencies. IEEE Transactions on Computers, 50(9):865{876, September 2001.
[14] Abraham Silbersc hatz, Peter Galvin, and Greg Gagne. Applied Operating System Concepts. John Wiley& Sons, New York, NY, rst edition, 2000
[2] K. Mani Chandy, Jayadev Misra, and Laura M. Haas. Distributed deadlock detection. ACM Transactions on Computer Systems, 1(2):144-156, May 1983
[3] Edsger Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643-644, November 1974.
[4] Mitchell Flatebo and Ajoy Kumar Datta. Self-stabilizing deadlock detection algorithms. In Proceedings of the1992 ACM Annual Conference on Communications, pages 117-122, Kansas City, Missouri, April 1992.
[5] Sukumar Ghosh and Arobinda Gupta. An exercise in fault-containment: self-stabilizing leader election. Information Processing Letters, 59(5):281{288, September 1996.
[6] José R. González de Mendívil, Federico Farina, José R. Garitagoitia, C. F. Alastruey , and J. M. Bernabeu-Auban. A distributed deadlock resolution algorithm for the AND model. IEEE Transactions on Parallel and Distributed Systems, 10(5):433{447, May 1999.
[7] T. Herman and K. Chandy. A distributed procedure to detect AND/OR deadlock. Technical Report TRLCS-8301, Department of Computer Science, University of Texas, Austin, Texas, 1983.
[8] Richard C.Holt. Some deadlock properties on computer systems. ACM Computing Surveys, 4(3):179-196, September 1972.
[9] Mehmet H. Karaata and Jeffery C. Line. Self-stabilizing algorithms for deadlock detection and identification in distributed systems. In Proceedings of the ISCA Thirteenth International Conference on Parallel and Distributed Computing, pages 320-325, Las Vegas, Nevada, August 2000.
[10] Edgar Knapp. Deadlock detection in distributed databases. ACM Computing Surveys, 19(4):303{328, December 1987.
[11] N. Natarajan. A distributed scheme for detecting communication deadlocks.IEEE Transactions on Software Engineering, SE- 12(4):531{537, April 1986.
[12] Marco Schneider. Self-stabilization. ACM Computing Surveys, 25(1):45{67, March 1993.
[13] Loren Schwiebert. Deadlock-free oblivious wormhole routing with cyclic dependencies. IEEE Transactions on Computers, 50(9):865{876, September 2001.
[14] Abraham Silbersc hatz, Peter Galvin, and Greg Gagne. Applied Operating System Concepts. John Wiley& Sons, New York, NY, rst edition, 2000
Downloads
Published
2003-10-01
Issue
Section
Original Articles
License
How to Cite
[1]
“Dynamic deadlock detection under the OR requirement model”, JCS&T, vol. 3, no. 02, pp. p. 38–44, Oct. 2003, Accessed: Jan. 14, 2026. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/937
