Paper Info
Title
Deadlock resolution in wait-for graphs by vertex/arc deletion.
Abstract
A deadlock occurs in a distributed computation if a group of processes wait indefinitely for resources from each other. In this paper we study actions to be taken after deadlock detection, especially the action of searching for a small deadlock-resolution set. More precisely, given a “snapshot” graph G representing a deadlocked state of a distributed computation governed by a certain deadlock model \({\mathbb {M}}\), we investigate the complexity of vertex/arc deletion problems that aim at finding minimum vertex/arc subsets whose removal turns G into a deadlock-free graph (according to model \({\mathbb {M}}\)). Our contributions include polynomial-time algorithms and hardness proofs, for general graphs and for special graph classes. Among other results, we show that the arc deletion problem in the OR model can be solved in polynomial time, and the vertex deletion problem in the OR model remains NP-complete even for graphs with maximum degree \({\varDelta }(G) = 4\), but is solvable in \(O (m \sqrt{n})\) time for graphs with \({\varDelta }(G)\le 3\).
Year
DOI
Venue
2019
10.1007/s10878-018-0279-5
J. Comb. Optim.
Keywords
Field
DocType
Deadlock resolution, Knot, Deadlock recovery, Wait-for graphs, Computational complexity, Vertex deletion, Directed feedback vertex set
Combinatorics,Arc (geometry),Vertex (geometry),Deadlock,Degree (graph theory),Deadlock prevention algorithms,Time complexity,Mathematics,Computation,Computational complexity theory
Journal
Volume
Issue
ISSN
37
2
1573-2886
Citations 
PageRank 
References 
1
0.35
13
Authors
3
Name
Order
Citations
PageRank
Alan Diêgo Aurélio Carneiro120.71
Fábio Protti235746.14
Uéverton S. Souza32021.12