A distributed algorithm for deadlock detection and resolution

ABSTRACT

This paper presents two distributed algorithms for detecting and resolving deadlocks. By insuring that only one of the deadlock processes will detect it, the problem of resolving the deadlock is simplified. That process could simply abort itself. In one version of the algorithm, an arbitrary process detects deadlock; and in a second version, the process with the lowest priority detects deadlock.

REFERENCES

• 1: Bracha, Gabriel, Sam Toueg, "A Distributed Algorithm For Generalized Deadlock Detection," TR 83-558, June 1983, Department of Computer Science, Cornell University.
• 2: K. M. Chandy , J. Misra, A distributed algorithm for detecting resource deadlocks in distributed systems, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.157-164, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806693]
• 3: Change, Ernest J. H., "Echo Algorithms: Depth Parallel Operations on General Graphs," IEEE Transactions on Software Engineering, Vol. SE-8, No. 4, July 1982.
• 4: Dijkstra, Edsger W., C. S. Scholten, "Termination Detection for Diffusing Computations," Information Processing Letters, Vol. 11, No. 1, August 1980.
• 5: Gligor, Virgil and Susan H. Shattuck, "On Deadlock Detection in Distributed Systems," IEEE Transactions on Software Engineering, Vol. SE-6, No. 5, September 1980.
• 6: 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.
• 7: Ron Obermarck, Distributed deadlock detection algorithm, ACM Transactions on Database Systems (TODS), v.7 n.2, p.187-208, June 1982 [doi>10.1145/319702.319717]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Deadlocks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Management