article

Open access

A distributed deadlock detection algorithm for CSP-like communication

Editor: Susan L. Graham Author:

S. -T. HuangAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 12, Issue 1

Pages 102 - 122

https://doi.org/10.1145/77606.77611

Published: 03 January 1990 Publication History

PDF eReader

Abstract

An algorithm for detecting deadlocks in distributed systems with CSP-like communication is proposed. Unlike previous work, the proposed algorithm avoids periodically sending deadlock-detecting messages by the processes and requires no local storage for the processes with size predetermined by the number of processes in the system. The algorithm is proven to have the following properties: (0) it never detects false deadlocks; (1) it has only one process in a knot report the deadlock; and (2) it detects every true deadlock in finite time.

References

[1]

BADAL, D. Z. The distributed deadlock detection algorithm. ACM Trans. Comput. Syst. 4, 4 (Nov. 1986), 320-337.

Crossref

Google Scholar

[2]

CHANDY, K. M., MISRA, J., AND HAAS, r. M. Distributed deadlock detection. ACM Trans. Comput. Syst. 1, 2 (May 1983), 144-156.

Crossref

Google Scholar

[3]

CHANDY, K. M., AND MISRA, J. A distributed algorithm for detecting resource deadlocks in distributed systems. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Aug. 1982). ACM, New York, 1982, 157-164.

Crossref

Google Scholar

[4]

CIDON, I., JArFE, J. M., AND SIDI, M. Local distributed deadlock detection by cycle detection and clustering. IEEE Trans. Softw. Eng. 13 (Jan. 1987), 3-14.

Crossref

Google Scholar

[5]

DIJKSTRA, E. W., FEIJEN, W. H. J., AND VAN GASTEREN, A. J.U. Derivation of a termination detection algorithm for distributed computations. Inf. Process. Lett. 16 (June 1983), 217-219.

Google Scholar

[6]

DIJKSTRA, E. W., AND SCHOLTEN, C. S. Termination detection for distributed computations. Inf. Process. Lett. 1l (Aug. 1980), 1-4.

Google Scholar

[7]

FRANCEZ, N. Distributed termination. ACM Trans. Program. Lang. Syst. 2 (Jan. 1980), 42-55.

Crossref

Google Scholar

[8]

FRANCEZ, N., AND RODEH, M. Achieving distributed termination without freezing. IEEE Trans. Softw. Eng. 8 (Mar. 1982), 287-292.

Google Scholar

[9]

HOARE, C. A. R. Communicating sequencial processes. Commun. ACM 21, 8 (Aug. 1978), 666-677.

Crossref

Google Scholar

[10]

HUANG, S.T. A fully distributed termination detection scheme. Inf. Process. Lett. 29 (Sept. 1988), 13-18.

Crossref

Google Scholar

[11]

KATZ, S., AND SHMUELI, O. Cooperative distributed algorithms for dynamic cycle prevention. IEEE Trans. Softw. Eng. 13 (May 1987), 540-552.

Crossref

Google Scholar

[12]

LAMPORT, r. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.

Crossref

Google Scholar

[13]

MISRA, J., AND CHANDY, K.M. A distributed graph algorithm: Knot detection. ACM Trans. Program. Lang. Syst. 4, 4 (Oct. 1982), 678-686.

Crossref

Google Scholar

[14]

MISRA, J., AND CHANDY, K.M. Termination detection of diffusing computations in communicating sequential processes. ACM Trans. Program. Lang. Syst. 4, 1 (Jan. 1982), 37-43.

Crossref

Google Scholar

[15]

NATARAJAN, N. A distributed scheme for detecting communication deadlocks. IEEE Trans. Sofiw. Eng. 12 (Apr. 1986), 531-537.

Crossref

Google Scholar

[16]

OBERMARCK, R. Distributed deadlock detection algorithm. ACM Trans. Database Syst. 7, 2 (June 1982), 187-208.

Crossref

Google Scholar

[17]

RANA, S.P. A distributed solution to the distributed termination problem. Inf. Process. Lett. 17 (July 1983), 43-46.

Google Scholar

[18]

TOPOR, R.W. Termination detection for distributed computations. Inf. Process. Lett. 18 (Jan. 1984), 33-36.

Google Scholar

Cited By

View all

Yuan TLi GLu JLiu CLi LXue J(2021)GoBench: A Benchmark Suite of Real-World Go Concurrency Bugs2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO51591.2021.9370317(187-199)Online publication date: 27-Feb-2021
https://doi.org/10.1109/CGO51591.2021.9370317
Ng NYoshida NZaks AHermenegildo M(2016)Static deadlock detection for concurrent go by global session graph synthesisProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892232(174-184)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892232
Stadtmüller KSulzmann MThiemann P(2016)Static Trace-Based Deadlock Analysis for Synchronous Mini-GoProgramming Languages and Systems10.1007/978-3-319-47958-3_7(116-136)Online publication date: 9-Oct-2016
https://doi.org/10.1007/978-3-319-47958-3_7
Show More Cited By

Index Terms

A distributed deadlock detection algorithm for CSP-like communication

Recommendations

A Priority Based Distributed Deadlock Detection Algorithm

Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed ...
False Deadlock Detection in Distributed Systems
Annals of discrete mathematics, 24

Detecting a nonexistent deadlock in distributed systems has been referred to as false deadlock detection. This correspondence shows that false deadlock wi1l never occur in a system of two-phase locking transactions. We also describe an algorithm to ...
Sufficient Condition for a Communication Deadlock and Distributed Deadlock Detection

The necessary and sufficient condition for deadlock in a distributed system and an algorithm for detection of a distributed deadlock based on the sufficient condition are formulated. The protocol formulated, checks all wait-for contiguous requests in ...

Reviews

Reviewer: John George Fletcher

Asynchronously executing processes that communicate by exchanging messages can deadlock if some subset of them form a knot of processes, each waiting to receive a message from another. Huang describes a distributed algorithm that detects all such knots exactly once. The description is given both informally and formally, and a rather formal proof of correctness is given. While including a formal presentation is certainly appropriate, I found the informal description to be more comprehensible and informal reasoning based on it to be more convincing (not an unexpected finding, based on past experience). The paper discusses possible difficulties in implementing the algorithm and compares the current work in some detail with previous work by others. A reading of the paper should be well worth the time of those interested in deadlocks.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 12, Issue 1

Jan. 1990

141 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/77606

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1990

Published in TOPLAS Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
775
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)13

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yuan TLi GLu JLiu CLi LXue J(2021)GoBench: A Benchmark Suite of Real-World Go Concurrency Bugs2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO51591.2021.9370317(187-199)Online publication date: 27-Feb-2021
https://doi.org/10.1109/CGO51591.2021.9370317
Ng NYoshida NZaks AHermenegildo M(2016)Static deadlock detection for concurrent go by global session graph synthesisProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892232(174-184)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892232
Stadtmüller KSulzmann MThiemann P(2016)Static Trace-Based Deadlock Analysis for Synchronous Mini-GoProgramming Languages and Systems10.1007/978-3-319-47958-3_7(116-136)Online publication date: 9-Oct-2016
https://doi.org/10.1007/978-3-319-47958-3_7
Ding ZZhou MWang S(2014)Ordinary Differential Equation-Based Deadlock DetectionIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2014.231175744:10(1435-1454)Online publication date: Oct-2014
https://doi.org/10.1109/TSMC.2014.2311757
Li CHuang LChen LLuo W(2013)Deadlock detection and recovery for component-based systemsMathematical and Computer Modelling10.1016/j.mcm.2012.12.03558:5-6(1362-1378)Online publication date: Sep-2013
https://doi.org/10.1016/j.mcm.2012.12.035
Li CHuang LChen LLuo W(2012)Using Dynamic Probe for Deadlock Detection in Component-Based SystemProceedings of the 2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing10.1109/IMIS.2012.13(292-299)Online publication date: 4-Jul-2012
https://dl.acm.org/doi/10.1109/IMIS.2012.13
Li CHuang LChen LLuo WLi X(2012)PBDDRProceedings of the 2012 19th Asia-Pacific Software Engineering Conference - Volume 0110.1109/APSEC.2012.33(790-795)Online publication date: 4-Dec-2012
https://dl.acm.org/doi/10.1109/APSEC.2012.33
Ding Z(2009)Static Analysis of Concurrent Programs Using Ordinary Differential EquationsProceedings of the 6th International Colloquium on Theoretical Aspects of Computing10.1007/978-3-642-03466-4_1(1-35)Online publication date: 12-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03466-4_1
(2005)Formal Requirements-Based Programming for Complex SystemsProceedings of the 10th IEEE International Conference on Engineering of Complex Computer Systems10.1109/ICECCS.2005.47(116-125)Online publication date: 16-Jun-2005
https://dl.acm.org/doi/10.1109/ICECCS.2005.47
Gracanin DSingh HHinchey MEltoweissy MBohner S(2005)A CSP-Based Agent Modeling Framework for the Cougaar Agent-Based ArchitectureProceedings of the 12th IEEE International Conference and Workshops on Engineering of Computer-Based Systems10.1109/ECBS.2005.6(255-262)Online publication date: 4-Apr-2005
https://dl.acm.org/doi/10.1109/ECBS.2005.6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

A Priority Based Distributed Deadlock Detection Algorithm

False Deadlock Detection in Distributed Systems

Sufficient Condition for a Communication Deadlock and Distributed Deadlock Detection

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations