Optimal deadlock resolutions in edge-disjoint reducible wait-for graphs

In a distributed computing system where resources are shared among geographically disparate processes, deadlock is of great concern for every process involved. Resolution of a deadlock requires that at least one process in the deadlock cycle be aborted and all resources held by the processor release...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1991-06, Vol.38 (6), p.307-313
Main Authors: Luo, Kenneth, Klostermeyer, William, Chow, Yuan-Chieh, Newman-Wolfe, Richard
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer programming
Computer science
Computer science
control theory
systems
Computer systems and distributed systems. User interface
deadlock resolution
Distributed systems
dominating set
edge-disjoint graph
Exact sciences and technology
Functions
Graphs
minimum abort set
minimum feedback vertex set
resource allocation
Software
Studies
Theory
wait-for graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In a distributed computing system where resources are shared among geographically disparate processes, deadlock is of great concern for every process involved. Resolution of a deadlock requires that at least one process in the deadlock cycle be aborted and all resources held by the processor released. A minimal number of processes should be aborted. The interprocess state of a system can be represented as a wait-for graph, reducing the problem to finding a minimal set of nodes such that elimination of the nodes yields a cycle-free graph. Wait-for graphs that are edge-joint reducible were recently considered. The problem of finding the minimum abort set was shown to be polynomial-time solvable for such graphs.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(91)90087-X