Abstract
This article introduces a self-stabilizing 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. Because of the self-stabilization property, the algorithm supports dynamic changes in the wait-for graph on which it works, and transient faults; also, it can be started in an arbitrary state. Previous deadlock-detection algorithms for the OR model are not guaranteed to recover from transient faults, nor can they be started in an arbitrary state. Once the algorithm terminates, each process knows if it is or not deadlocked; moreover, deadlocked processes know whether they cause or only suffer from deadlock.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Knapp, E.: Deadlock detection in distributed databases. ACM Computing Surveys 19(4), 303–328 (1987)
Flatebo, M., Datta, A.K.: Self-stabilizing deadlock detection algorithms. In: Proceedings of the 1992 ACM Annual Conference on Communications, Kansas City, Missouri, pp. 117–122 (1992)
Karaata, M.H., Line, J.C.: Self-stabilizing algorithms for deadlock detection and identification in distributed systems. In: Proceedings of the ISCA Thirteenth International Conference on Parallel and Distributed Computing, Las Vegas, Nevada, pp. 320–325 (2000)
Chandy, K.M., Misra, J., Haas, L.M.: Distributed deadlock detection. ACM Transactions on Computer Systems 1(2), 144–156 (1983)
Cidon, I., Jaffe, J.M., Sidi, M.: Local distributed deadlock detection by knot detection. In: Proceedings of the ACM SIGCOMM Conference on Communications Architecture & Protocols, pp. 377–384. ACM Press, New York (1986)
Lee, S., Lee, Y.: A distributed algorithm for deadlock detection under OR-request model. In: Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, pp. 298–299. IEEE Press, Los Alamitos (work in progress, fast abstracts, 1999)
Natarajan, N.: A distributed scheme for detecting communication deadlocks. IEEE Transactions on Software Engineering SE-12(4), 531–537 (1986)
Herman, T., Chandy, K.: A distributed procedure to detect AND/OR deadlock. Technical Report TR LCS-8301, Department of Computer Science, University of Texas, Austin, Texas (1983)
Bracha, G., Toueg, S.: A distributed algorithm for generalized deadlock detection. In: Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, pp. 285–301 (1984)
Dijkstra, E.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17(11), 643–644 (1974)
Schneider, M.: Self-stabilization. ACM Computing Surveys 25(1), 45–67 (1993)
Schwiebert, L.: Deadlock-free oblivious wormhole routing with cyclic dependencies. IEEE Transactions on Computers 50(9), 865–876 (2001)
Holt, R.C.: Some deadlock properties of computer systems. ACM Computing Surveys 4(3), 179–196 (1972)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Orellana, C.F., Ruz, C., Eterovic, S.Y. (2006). Self-stabilizing Deadlock Detection Under the OR Requirement Model. In: Nagel, W.E., Walter, W.V., Lehner, W. (eds) Euro-Par 2006 Parallel Processing. Euro-Par 2006. Lecture Notes in Computer Science, vol 4128. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11823285_58
Download citation
DOI: https://doi.org/10.1007/11823285_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37783-2
Online ISBN: 978-3-540-37784-9
eBook Packages: Computer ScienceComputer Science (R0)