A distributed deadlock detection algorithm: Distributed graph reconstruction algorithm (Q1119017)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A distributed deadlock detection algorithm: Distributed graph reconstruction algorithm |
scientific article; zbMATH DE number 4096769
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A distributed deadlock detection algorithm: Distributed graph reconstruction algorithm |
scientific article; zbMATH DE number 4096769 |
Statements
A distributed deadlock detection algorithm: Distributed graph reconstruction algorithm (English)
0 references
1989
0 references
A new algorithm for the distributed deadlock detection problem in the communication model of a distributed system is described. The new algorithm is called distributed graph reconstruction (DGR) algorithm. To represent the state of the system, a Wait-For-Graph is used. Doing the reconstruction of the Wait-For-Graph a cycle can be detected in the graph. The DGR algorithm can detect all existing deadlocks and does not detect false deadlock. The algorithm detects the deadlock with the complexity of messages \(O(n^ 2)\).
0 references
communication deadlock
0 references
deadlock detection
0 references
distributed system
0 references
Wait-For- Graph
0 references
