ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Distributed deadlock detection
Full text PdfPdf (856 KB)
Source ACM Transactions on Computer Systems (TOCS) archive
Volume 1 ,  Issue 2  (May 1983) table of contents
Pages: 144 - 156  
Year of Publication: 1983
ISSN:0734-2071
Authors
K. Mani Chandy  Department of Computer Sciences, University of Texas at Austin, Austin, TX
Jayadev Misra  Department of Computer Sciences, University of Texas at Austin, Austin, TX
Laura M. Haas  IBM Research, 5600 Cottle Road, San Jose, CA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 43,   Downloads (12 Months): 239,   Citation Count: 62
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/357360.357365
What is a DOI?

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
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]
 
2
DIJKSTRA, E.W., AND SCHOLTEN, C.S. Termination detection for diffusing computations. Inf. Process. Lett. 11, 1 (Aug. 1980), 1-4.
 
3
GLIGOR, V.D., AND SHATTUCK, S.H. Deadlock detection in distributed systems. IEEE Trans. Softw. Eng. SE-6, 5 (Sept. 1980), 435-440.
 
4
B. Goldman, DEADLOCK DETECTION IN COMPUTER NETWORKS, Massachusetts Institute of Technology, Cambridge, MA, 1977
 
5
Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
 
6
Laura Myers Haas, Two approaches to deadlock in distributed systems, 1981
7
C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978  [doi>10.1145/359576.359585]
 
8
ISLOOR, S.S., AND MARSLAND, T.A. An effective 'on-line' deadlock detection technique for distributed database management systems. In Proc. COMPSAC 1978, IEEE, New York, pp. 283- 288.
9
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]
 
10
LOMET, D.B. Coping with deadlock in distributed systems. Res. Rep. RC 7460 (#32196), IBM, T. J. Watson Research Center, Yorktown Heights, N.Y., Dec. 1978.
 
11
MAHOUD, S.A., AND RIORDON, J.S. Software controlled access to distributed databases. INFOR 15, 1 (Feb. 1977), 22-36.
 
12
MENASCE, D., AND MUNTZ, R. Locking and deadlock detection in distributed databases. IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 195-202.
13
Jayadev Misra , K. M. Chandy, Termination Detection of Diffusing Computations in Communicating Sequential Processes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.37-43, Jan. 1982  [doi>10.1145/357153.357156]
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]
 
15
CHANDY, K.M., AND MISRA, J. Deadlock absence proofs for networks of communicating processes. Inf. Process. Lett. 9, 4 (Nov. 1979), 185-189.

CITED BY  62
Mani Chandy , Jayadev Misra, An example of stepwise refinement of distributed programs: quiescence detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.326-343, July 1986
Shmuel Katz, A superimposition control construct for distributed systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.337-356, April 1993
Andrew S. Tanenbaum , Robbert Van Renesse, Distributed operating systems, ACM Computing Surveys (CSUR), v.17 n.4, p.419-470, Dec. 1985
Yuri Breitbart , Henry F. Korth, Replication and consistency: being lazy helps sometimes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.173-184, May 11-15, 1997, Tucson, Arizona, United States
Hui Wu , Wei-Ngan Chin , Joxan Jaffar, An Efficient Distributed Deadlock Avoidance Algorithm for the AND Model, IEEE Transactions on Software Engineering, v.28 n.1, p.18-29, January 2002
Paul Hudak, Distributed task and memory management, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.277-289, August 17-19, 1983, Montreal, Quebec, Canada
C. P. Wang , V. O. K. Li, The precedence-assignment model for distributed databases concurrency control algorithms, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.119-128, March 23-25, 1987, San Diego, California, United States
Gabriel Bracha , Sam Toueg, A distributed algorithm for generalized deadlock detection, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.285-301, August 27-29, 1984, Vancouver, British Columbia, Canada
Jayadev Misra, Detecting termination of distributed computations using markers, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.290-294, August 17-19, 1983, Montreal, Quebec, Canada
Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986
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
Kia Makki , Niki Pissinou, Detection and resolution of deadlocks in distributed database systems, Proceedings of the fourth international conference on Information and knowledge management, p.411-416, November 29-December 02, 1995, Baltimore, Maryland, United States
I Cidon , J M Jaffe, Local distributed deadlock detection by knot detection, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.377-384, Aug. 5, 1986
Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987
Chia-Shiang Shih , John A. Stankovic, Distributed deadlock detection in Ada run-time environments, Proceedings of the conference on TRI-ADA '90, p.362-375, December 03-06, 1990, Baltimore, Maryland, United States
S. -T. Huang, A distributed deadlock detection algorithm for CSP-like communication, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.102-122, Jan. 1990
Mitchell Flatebo , Ajoy Kumar Datta, Self-stabilizing deadlock detection algorithms, Proceedings of the 1992 ACM annual conference on Communications, p.117-122, March 03-05, 1992, Kansas City, Missouri, United States
Kenneth R. Wood , Stephen J. Turner, A generalized carrier-null method for conservative parallel simulation, ACM SIGSIM Simulation Digest, v.24 n.1, p.50-57, July 1994
M. Roesler , W. A. Burkhard, Semantic lock models in object-oriented distributed systems and deadlock resolution, ACM SIGMOD Record, v.17 n.3, p.361-370, June 1988
Meng-Lin Yu, En route to more efficient conservative parallel event simulation, Proceedings of the 25th annual symposium on Simulation, p.54-60, April 1992, Orlando, Florida, United States
J. Kent Peacock, Deadlock avoidance in loosely-coupled multiprocessors with finite buffer pools, ACM SIGOPS Operating Systems Review, v.23 n.2, p.20-24, April 1989
Azzedine Boukerche , Carl Tropper, A Distributed Graph Algorithm for the Detection of Local Cycles and Knots, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.748-757, August 1998
Kurt Schelfthout , Tom Holvoet, Coordination middleware for decentralized applications in dynamic networks, Proceedings of the 2nd international doctoral symposium on Middleware, p.1-5, November 28-December 02, 2005, Grenoble, France
Meng-Lin Yu , Sumit Ghosh , Erik DeBenedictis, A provably correct, non-deadlocking parallel event simulation algorithm, Proceedings of the 24th annual symposium on Simulation, p.100-111, April 1991, New Orleans, Louisiana, United States
Soojung Lee , Junguk L. Kim, Performance Analysis of Distributed Deadlock Detection Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.623-636, July 2001
The Journal of Supercomputing staff, The Performance of an Efficient Distributed Synchronization and Recovery Algorithm, The Journal of Supercomputing, v.19 n.2, p.199-219, June 2001
K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985
Sumit Ghosh , Meng-Lin Yu, An Asynchronous Distributed Approach for the Simulation of Behavior-Level Models on Parallel Processors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.6, p.639-652, June 1995
M. Roesler , W. A. Burkhard, Resolution of Deadlocks in Object-Oriented Distributed Systems, IEEE Transactions on Computers, v.38 n.8, p.1212-1224, August 1989
Alokdhar N. Choudhary , Walter H. Kohler , John A. Stankovic , Don Towsley, A Modified Priority Based Probe Algorithm for Distributed Deadlock Detection and Resolution, IEEE Transactions on Software Engineering, v.15 n.1, p.10-17, January 1989
Waleed A. Muhanna, Composite Programs: Hierarchical Construction, Circularity, and Deadlocks, IEEE Transactions on Software Engineering, v.17 n.4, p.320-333, April 1991
J. Błażewicz , D. P. Bovet , J. Brzeziński , G. Gambosi , M. Talamo, Optimal Centralized Algorithms for Store-And-Forward Deadlock Avoidance, IEEE Transactions on Computers, v.43 n.11, p.1333-1338, November 1994
Sugath Warnakulasuriya , Timothy Mark Pinkston, A Formal Model of Message Blocking and Deadlock Resolution in Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.212-229, March 2000
M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989
Ajay D. Kshemkalyani , Mukesh Singhal, A One-Phase Algorithm to Detect Distributed Deadlocks in Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.880-895, November 1999
Sumit Ghosh, P2EDAS: Asynchronous, Distributed Event Driven Simulation Algorithm with Inconsistent Event Preemption for Accurate Execution of VHDL Descriptions on Parallel Processors, IEEE Transactions on Computers, v.50 n.1, p.28-50, January 2001
Carl Tropper, Parallel discrete-event simulation applications, Journal of Parallel and Distributed Computing, v.62 n.3, p.327-335, March 2002
Daniel A. Reed , Allen D. Malony , Bradley McCredie, Parallel Discrete Event Simulation Using Shared Memory, IEEE Transactions on Software Engineering, v.14 n.4, p.541-553, April 1988
Bernhard Nebel, Cooperating physical robots: a lesson in playing robotic soccer, Mutli-agents systems and applications, Springer-Verlag New York, Inc., New York, NY, 2001
V. K. Garg , J. Ghosh, Repeated Computation of Global Functions in a Distributed Environment, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.823-834, August 1994
Ugur Halici , Asuman Dogac, An Optimistic Locking Technique for Concurrency Control in Distributed Databases, IEEE Transactions on Software Engineering, v.17 n.7, p.712-724, July 1991
B. E. Wojcik , Z. M. Wojcik, Sufficient Condition for a Communication Deadlock and Distributed Deadlock Detection, IEEE Transactions on Software Engineering, v.15 n.12, p.1587-1595, December 1989
Jesús Villadangos , Federico Fariña , José Ramón González de Mendívil , José Ramón Garitagoitia , Alberto Córdoba, A Safe Algorithm for Resolving OR Deadlocks, IEEE Transactions on Software Engineering, v.29 n.7, p.608-622, July 2003
B. -C. Jenq , B. C. Twichell , T. W. Keller, Locking Performance in a Shared Nothing Parallel Database Machine, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.530-543, December 1989
Jen-Yao Chung , Jane W. S. Liu , Kwei-Jay Lin, Scheduling Periodic Jobs that Allow Imprecise Results, IEEE Transactions on Computers, v.39 n.9, p.1156-1174, September 1990
Y. C. Tay , W. Tim Loke, On deadlocks of exclusive AND-requests for resources, Distributed Computing, v.9 n.2, p.77-94, October 1995
Jean-Michel Hélary , Michel Raynal, Towards the construction of distributed detection programs, with an application to distributed termination, Distributed Computing, v.7 n.3, p.137-147, March 1994
André Schiper , Alain Sandoz, Strong stable properties in distributed systems, Distributed Computing, v.8 n.2, p.93-103, October 1994
Shigang Chen , Yibei Ling, Stochastic analysis of distributed deadlock scheduling, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
Keith Marzullo , Laura S. Sabel, Efficient detection of a class of stable properties, Distributed Computing, v.8 n.2, p.81-91, October 1994
Bao-Chyuan Jenq , Walter H. Kohler , Don Towsley, A Queueing Network Model for a Distributed Database Testbed System, IEEE Transactions on Software Engineering, v.14 n.7, p.908-921, July 1988
Erik DeBenedictis , Sumit Ghosh , Meng-Lin Yu, A Novel Algorithm for Discrete-Event Simulation: Asynchronous Distributed Discrete-Event Simulation Algorithm for Cyclic Circuits Using a Dataflow Network, Computer, v.24 n.6, p.21-33, June 1991
Gerard Tel , Friedemann Mattern, The derivation of distributed termination detection algorithms from garbage collection schemes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.1-35, Jan. 1993
Soojung Lee , Kil Hong Joo, Efficient detection and resolution of OR deadlocks in distributed systems, Journal of Parallel and Distributed Computing, v.65 n.9, p.985-993, September 2005
Sharon Simmons , Dennis Edwards, Quantitative causality, Neural, Parallel & Scientific Computations, v.15 n.1, p.103-124, March 2007
Natalija Krivokapić , Alfons Kemper , Ehud Gudes, Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.2, p.79-100, October 1999
P. Krishna Reddy , Subhash Bhalla, Deadlock prevention in a distributed database system, ACM SIGMOD Record, v.22 n.3, p.40-46, Sept. 1993
Ahmed K. Elmagarmid, A survey of distributed deadlock detection algorithms, ACM SIGMOD Record, v.15 n.3, p.37-45, Sept. 1986
Chim-fu Yeung , Sheung-lun Hung , Kam-yiu Lam, Performance evaluation of a new distributed deadlock detection algorithm, ACM SIGMOD Record, v.23 n.3, p.21-26, Sept. 1994
M. Uehara , C. Numaoka , Y. Yokote , M. Tokoro, Sarek: a window system interface for object-oriented concurrent programming languages, ACM SIGPLAN Notices, v.24 n.4, p.187-189, April 1989
Yibei Ling , Shigang Chen , Cho-Yu Jason Chiang, On Optimal Deadlock Detection Scheduling, IEEE Transactions on Computers, v.55 n.9, p.1178-1187, September 2006
Gaurav Sharma , Jos Martin, MATLAB®: a language for parallel computing, International Journal of Parallel Programming, v.37 n.1, p.3-36, February 2009

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Deadlocks; Synchronization
      D.4.4 Communications Management
          Subjects: Network communication


General Terms:
Algorithms


Keywords:
communication deadlock, distributed deadlock detection, message communication systems, resource deadlock

Collaborative Colleagues:
K. Mani Chandy: colleagues
Jayadev Misra: colleagues
Laura M. Haas: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player