A distributed algorithm for generalized deadlock detection

ABSTRACT

An efficient distributed algorithm to detect deadlocks in distributed and dynamically changing systems is presented. In our model, processes can request any N available resources from a pool of size M. This is a generalization of the well-known AND-OR request model. The algorithm is incrementally derived and proven correct. Its communication, computational, and space complexity compares favorably with those of previously known distributed AND-OR deadlock detection algorithms.

REFERENCES

• 1: C. Beeri and R. Obermarck, A resource class independent deadlock detection algorithm, Research Report RJ3077, IBM Research Laboratory, San Jose, California, May 1981.
• 2: G. Bracha and S. Toueg, A distributed algorithm for generalized deadlock detection, Technical Report TR 83-558, Cornell University, June 1983.
• 3: E. Chang, Echo algorithms: depth parallel operations on general graphs, IEEE Transactions on Software Engineering, vol. SE-8, no. 4, pp. 391-401, July 1980.
• 4: 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]
• 5: K. Mani Chandy , Jayadev Misra , Laura M. Haas, Distributed deadlock detection, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.144-156, May 1983 [doi>10.1145/357360.357365]
• 6: M. Chandy, Presentation given at Cornell University.
• 7: M. Chandy and L. Lamport, Detecting stability in distributed systems, to be published.
• 8: L. Haas and C. Mohan, A distributed deadlock detection algorithm for a resource-based system, Research Report RJ3765, IBM Research Laboratory, San Jose, California, Jan. 1983.
• 9: T. Herman and M. Chandy, A distributed procedure to detect AND/OR deadlock, University of Texas, Dept of Computer Sciences, TR LCS-8301, Feb. 1983.
• 10: Richard C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys (CSUR), v.4 n.3, p.179-196, Sept. 1972 [doi>10.1145/356603.356607]
• 11: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 12: D. Menasce and R. Muntz, Locking and deadlock detection in distributed data bases, IEEE Transaction on So 195-202, Engineering, vol. 5, no. 3, pp. 195-202, May 1979.
• 13: R. Obermarck, Deadlock detection for all resource classes, Research Report RJ 2955, IBM Research Laboratory, San Jose, California, Oct. 1980.
• 14: 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:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

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

General Terms:
Design, Management