Distributed deadlock detection algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Distributed deadlock detection algorithm

Full text

Pdf (1.55 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 7 , Issue 2 (June 1982) table of contents

Pages: 187 - 208

Year of Publication: 1982

ISSN:0362-5915

Author

Ron Obermarck

IBM, San Jose, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 227, Citation Count: 46

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/319702.319717 What is a DOI?

ABSTRACT

We propose an algorithm for detecting deadlocks among transactions running concurrently in a distributed processing network (i.e., a distributed database system). The proposed algorithm is a distributed deadlock detection algorithm. A proof of the correctness of the distributed portion of the algorithm is given, followed by an example of the algorithm in operation. The performance characteristics of the algorithm are also presented.

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	GLIGOR, V.D., AND SHATTUCK, S.H. On deadlock detection in distributed systems. Computer Science Tech. Rep. 837, University of Maryland, College Park, Md., Dec. 1979.
	2	B. Goldman, DEADLOCK DETECTION IN COMPUTER NETWORKS, Massachusetts Institute of Technology, Cambridge, MA, 1977
	3	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	4	GRAY, J.N. A discussion of distributed systems. Res. Rep. RJ2699(34594), IBM Research Division, Sept. 1979.
	5	GRAY, J.N., HOMAN, P., OBE~ARCK, R., AND KORTH, H. A straw man analysis of probability of waiting and deadlock. Res. Rep. RJ3066(38112), IBM Research Division, Feb. 1981 (presented at the 5th Berkeley Workshop on Distributed Data Management and Computer Networks, Feb. 198i).
	6	JOHNSON, D.B. Finding all the elementary cycles of a directed graph. SIAM Comput. 4, 1 (March 1975), 77-84.
	7	MENASCE, D., AND MUNTZ, R. Locking and deadlock detection in distributed data bases. IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 195-202.
	8	OBERMARCK, R. Distributed data base. IBM Palo Alto Systems Center Tech. Bull. G320-6019, IBM, Palo Alto, Calif., Sept. 1978.
	9	Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]

CITED BY 46

	C. Mohan , B. Lindsay , R. Obermarck, Transaction management in the R* distributed database management system, ACM Transactions on Database Systems (TODS), v.11 n.4, p.378-396, Dec. 1986
	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
	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
	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
	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
	Don P. Mitchell , Michael J. Merritt, A distributed algorithm for deadlock detection and resolution, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.282-284, August 27-29, 1984, 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
	Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987
	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
	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
	José Ramón González de Mendívil , Federico Fariña , José Ramó Garitagoitia , Carlos F. Alastruey , J. M. Bernabeu-Auban, A Distributed Deadlock Resolution Algorithm for the AND Model, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.433-447, May 1999
	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
	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
	Alfred Z. Spector , Dean Daniels , Daniel Duchamp , Jeffrey L. Eppinger , Randy Pausch, Distributed transactions for reliable systems, ACM SIGOPS Operating Systems Review, v.19 n.5, p.127-146, Dec. 1-4, 1985
	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
	Frank Schmuck , Jim Wylie, Experience with transactions in QuickSilver, ACM SIGOPS Operating Systems Review, v.25 n.5, p.239-253, Oct. 1991
	Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983
	R. Haskin , Y. Malachi , W. Sawdon , G. Chan, Recovery management in QuickSilver, ACM SIGOPS Operating Systems Review, v.21 n.5, p.107-108, Nov. 1987
	Rober Haskin , Yoni Malachi , Gregory Chan, Recovery management in QuickSilver, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.82-108, Feb. 1988
	Andrew S. Tanenbaum , Robbert Van Renesse, Distributed operating systems, ACM Computing Surveys (CSUR), v.17 n.4, p.419-470, Dec. 1985
	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
	John Thangarajah , Lin Padgham , Michael Winikoff, Detecting & exploiting positive goal interaction in intelligent agents, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	Henry F. Korth , Ravi Krishnamurthy , Anil Nigam , John T. Robinson, A framework for understanding distributed (deadlock detection) algorithms, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Bruce G. Lindsay , Laura M. Haas , C. Mohan , Paul F. Wilms , Robert A. Yost, Computation and communication in R*: a distributed database manager, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.24-38, February 1984
	D. Kumar, Development of a Class of Distributed Termination Detection Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.4 n.2, p.145-155, April 1992
	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
	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
	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
	Pentti A. Honkanen, Concurrency control and integrity preservation for the `RIM' DBMS, ACM SIGMIS Database, v.15 n.3, p.34-39, Spring 1984
	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
	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
	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
	M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989
	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
	A. K. Elmagarmid , A. K. Datta, Two-Phase Deadlock Detection Algorithm, IEEE Transactions on Computers, v.37 n.11, p.1454-1458, November 1988
	Klaus Haller , Heiko Schuldt , Can Türker, Decentralized coordination of transactional processes in peer-to-peer environments, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	D. Z. Badal, The distributed deadlock detection algorithm, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.320-337, Nov. 1986
	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
	Rex E. Gantenbein, An annotated bibliography of dependable distributed computing, ACM SIGOPS Operating Systems Review, v.26 n.2, p.60-81, April 1992
	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
	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
	J. P. Gray , P. J. Hansen , P. Homan , M. A. Lerner , M. Pozefsky, Advanced program-to-program communication in SNA, IBM Systems Journal, v.22 n.4, p.298-318, December 1983