Deletion Graph Problems Based on Deadlock Resolution
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.
Referências
V. C. Barbosa, A. D. A. Carneiro, F. Protti, and U. S. Souza. Deadlock models in distributed computation: foundations, design, and computational complexity. In Proceedings of the 31st Annual ACM Symposium on Applied Computing, pages 538–541. ACM, 2016.
P. Kolman and J. Kratochvíl. Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011, Revised Papers, volume 6986. Springer Science & Business Media, 2011.
D. P. Mitchell and M. J. Merritt. A distributed algorithm for deadlock detection and resolution. In Proceedings of the third annual ACM symposium on Principles of distributed computing, pages 282–284. ACM, 1984.
