Deletion Graph Problems Based on Deadlock Resolution

  • Alan Diêgo Aurélio Carneiro
  • Fábio Protti
  • Uéverton S. Santos

Resumo


A deadlock occurs in a distributed computing when a group of processes wait indefinitely for resources from each other. Such a property is stable, that is, once occurs into a global state it also will exist in any subsequent global state. Distributed computations are usually represented by wait-for graphs, where the behavior of processes is determined by a deadlock model. In this paper we consider the scenario where deadlock was detected in a system and then some deadlock-breaking set must be found and removed. Hence, given a “snapshot” G of a deadlocked distributed computation which operates according to a deadlock model M, we investigate the complexity of vertex deletion and arc deletion problems whose goal is to obtain the minimum number of removals in order to turn G free of graph structures that characterize deadlocks. The complexity of such problems depends on the deadlock model which governs the computation as well as the type of structure to be removed. The results of this paper are NP-completeness proofs and polynomial algorithms for general and particular graph classes. In special, we show that the arc deletion problem on the OR Model can be solved in polynomial time, and the vertex deletion problem on the OR Model remains NP-Complete even on graphs with (G) = 4, but it is solvable in polynomial time on graphs with (G) 3.

Publicado
06/07/2017
Como Citar

Selecione um Formato
CARNEIRO, Alan Diêgo Aurélio; PROTTI, Fábio; SANTOS, Uéverton S.. Deletion Graph Problems Based on Deadlock Resolution. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3178.