|
 ABSTRACT
This paper presents a distributed algorithm to detect deadlocks in distributed data bases. Features of this paper are (1) a formal model of the problem is presented, (2) the correctness of the algorithm is proved, i.e. we show that all true deadlocks will be detected and deadlocks will not be reported falsely, (3) no assumptions are made other than that messages are received correctly and in order and (4) the algorithm is simple.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Chandy, K. M., J. Misra and L. Haas, "A Distributed Deadlock Detection Algorithm and Its Correctness Proof," submitted to the Communications of the ACM.
|
| |
2
|
Dijkstra, E. W. D. and C. S. Scholten, "Termination Detection for Diffusing Computations," Information Processing Letters, 11, 1, August 1980, pp 1-4.
|
| |
3
|
Menasce, Daniel and Richard Muntz, "Locking and Deadlock Detection in Distributed Data Bases," IEEE Transactions on Software Engineering, Vol. SE-5, No. 3, May 1979.
|
| |
4
|
Gligor, Virgil and Susan H. Shattuck, "On Deadlock Detection in Distributed Systems," IEEE Transactions on Software Engineering, Vol. SE-6, No. 5, September 1980.
|
| |
5
|
|
| |
6
|
|
| |
7
|
Obermarck, Ron, "Global Deadlock Detection Algorithm," RJ2845, IBM Research Laboratory, San Jose, California 95193, June 1980.
|
| |
8
|
Mohan, C., "Distributed Data Base Management - Progress, Problems, Some Proposals and Future Directions," Computer Sciences Department, Working Paper WP-7802, University of Texas, Austin, Texas 78712, May 1979.
|
CITED BY 29
|
|
Baruch Awerbuch , Shay Kutten , David Peleg, Efficient deadlock-free routing, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.177-188, August 19-21, 1991, Montreal, Quebec, Canada
|
|
|
|
|
|
Young Chul Park , Peter Scheuermann , Hsiang Lung Tung, A distributed deadlock detection and resolution algorithm based on a hybrid wait-for graph and probe generation scheme, Proceedings of the fourth international conference on Information and knowledge management, p.378-386, November 29-December 02, 1995, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jean-Michael Helary , Claude Jard , Noël Plouzeau , Michel Raynal, Detection of stable properties in distributed applications, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.125-136, August 10-12, 1987, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.1