research-article

Sufficient Condition for a Communication Deadlock and Distributed Deadlock Detection

Authors:

B. E. Wojcik,

Z. M. WojcikAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 15, Issue 12

Pages 1587 - 1595

https://doi.org/10.1109/32.58770

Published: 01 December 1989 Publication History

Publisher Site

Abstract

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 one iteration. A cycle is detected when a query message reaches the initiator. A wait-for cycle is only the necessary condition for the distributed deadlock. A no-deadlock message is expected by the query initiator to infer a deadlock-free situation if at least one wait-for cycle is present. A no-deadlock message is issued by a dependent (query intercessor) that is not waiting-for. No no-deadlock message implies a deadlock, and processes listed in the received query messages are the processes involved in a distributed deadlock. Properties of the protocol are discussed. The authors show that a replication of a requested higher-priority (or older) process can prevent a distributed deadlock (in a continuous deadlock treatment). A replication is shown to recover (in a periodical deadlock handling) a sequence of processes from an indefinite wait-die scheme.

References

[1]

{1} K. M. Chandy and J. Misra, "Distributed deadlock detection," ACM Trans. Comput. Syst., vol. 1, pp. 144-156, May 1983.

Digital Library

Google Scholar

[2]

{2} H. M. Deitel, An Introduction to Operating Systems. Reading, MA: Addison-Wesley, 1984.

Google Scholar

[3]

{3} K. P. Eswaran and J. N. Gray, "The notions of consistency and predicate locks in a database system," Commun. ACM, vol. 19, pp. 624- 633, Nov. 1976.

Digital Library

Google Scholar

[4]

{4} C. A. R. Hoare, "Communicating sequential processes," Commun. ACM, vol. 21, no. 8, pp. 666-677, 1978.

Digital Library

Google Scholar

[5]

{5} G. S. Ho and C. V. Ramamoorthy, "Protocols for deadlock detection in distributed database systems," IEEE Trans. Software Eng., vol. SE-8, Nov. 1982.

Digital Library

Google Scholar

[6]

{6} R. C. Holt, "Some deadlock properties of computer system," Comput. Surveys, vol. 4, Sept. 1972.

Digital Library

Google Scholar

[7]

{7} W. H. Kohler, "A survey for techniques for synchronization and recovery in distributed computer systems," Comput. Surveys, vol. 13, no. 2, pp. 149-183, 1981.

Digital Library

Google Scholar

[8]

{8} R. Koo and S. Toueg, "Checkpointing and rollback--Recovery for distributed systems," IEEE Trans. Software Eng., vol. SE-13, no. 1, pp. 23-31, 1987.

Digital Library

Google Scholar

[9]

{9} D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, "System level concurrency control for distributed databases," ACM Trans. Data-base Syst., vol. 3, pp. 178-198, June 1978.

Digital Library

Google Scholar

[10]

{10} J. L. Peterson and A. Silberschatz, Operating System Concepts, 2nd ed. Reading, MA: Addison-Wesley, 1985.

Digital Library

Google Scholar

[11]

{11} D. Skeen, "A formal model of crash recovery in a distributed system," in Concurrency Control and Reliability in Distributed Systems, B. K. Bhargava, Ed. New York: Van Nostrand Reinhold, 1987, pp. 295-317.

Digital Library

Google Scholar

[12]

{12} B. Wojcik and Z. Wojcik, "Atomic send-receive checkpoint fault recovery," IEEE Trans. Software Eng., 1988, submitted for publication.

Google Scholar

Cited By

View all

Krishnamurthi MBasavatia AThallikar SSadowski DSeila A(1994)Deadlock detection and resolution in simulation modelsProceedings of the 26th conference on Winter simulation10.5555/193201.194334(708-715)Online publication date: 11-Dec-1994
https://dl.acm.org/doi/10.5555/193201.194334
Wójcik ZWójcik B(1991)Rough Grammar for Efficient and Fault-Tolerant Computing on a Distributed SystemIEEE Transactions on Software Engineering10.1109/32.8390217:7(652-668)Online publication date: 1-Jul-1991
https://dl.acm.org/doi/10.1109/32.83902

Index Terms

Sufficient Condition for a Communication Deadlock and Distributed Deadlock Detection
1. Networks
  1. Network protocols
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
        Process management
        Deadlocks
        Process synchronization

Recommendations

Distributed deadlock detection
A Distributed Deadlock Detection and Resolution Algorithm and its Correctness Proof

The key idea of the algorithm is to let one transaction controller be in charge of all transactions in a set of interacting transactions. Two transactions are interacting if they are both interested in (accessing) the same resource. In addition, the ...
A Queueing Network Model for a Distributed Database Testbed System

A queuing network model for analyzing the performance of a distributed database testbed system with a transaction workload is developed. The model includes the effects of the concurrency control protocol (two-phase locking with distributed deadlock ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 15, Issue 12

December 1989

160 pages

ISSN:0098-5589

Editor:
Victor R. Basili
Univ. Maryland, College Park

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Krishnamurthi MBasavatia AThallikar SSadowski DSeila A(1994)Deadlock detection and resolution in simulation modelsProceedings of the 26th conference on Winter simulation10.5555/193201.194334(708-715)Online publication date: 11-Dec-1994
https://dl.acm.org/doi/10.5555/193201.194334
Wójcik ZWójcik B(1991)Rough Grammar for Efficient and Fault-Tolerant Computing on a Distributed SystemIEEE Transactions on Software Engineering10.1109/32.8390217:7(652-668)Online publication date: 1-Jul-1991
https://dl.acm.org/doi/10.1109/32.83902

Abstract

References

Cited By

Index Terms

Recommendations

Distributed deadlock detection

A Distributed Deadlock Detection and Resolution Algorithm and its Correctness Proof

A Queueing Network Model for a Distributed Database Testbed System

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations