Detection of Inherent Deadlocks in Distributed Programs.
Abstract
In this paper, the concept of 'inherent deadlock' in distributed programs is defined. Several algorithms for detecting inherent deadlocks are given. Deadlock prevention is crucial in distributed programs. In order to ensure the correctness of a distributed program, we must avoid the occurrence of the deadlock in its execution. Unfortunately, the deadlock problem in distributed program is undecidable, as the halting problem in the sequential problem. However, partial solutions to the deadlock problem exist. In this the authors shall investigate the detection of inherent deadlocks in distributed programs. There are many models for distributed programs. In this paper, the authors shall use the model of Communicating Sequential Processes (CSP) developed by Hoare. In section 2 they develop some simplifications and abstractions of CSP and define the concept of 'inherent deadlock'. They solve its decision problem. In section 3 the authors define the concept of D-execution, and obtain a sufficient condition and a corresponding algorithm for detecting inherent deadlock. In sections 4 and 5 the authors introduce the concept 'matching number' as the foundation for obtaining two sufficient conditions for detecting inherent deadlock. Then they reduce these conditions to the solvability of some kind of indeterminate equation and give its decision algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1982
- Accession Number
- ADA120205
Entities
People
- Kegang Hao
- Raymond T. Yeh
Organizations
- University of Maryland