Deadlock resolution in wait-for graphs by vertex/arc deletion. (English) Zbl 1420.90075
Summary: 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\).
MSC:
| 90C35 | Programming involving graphs or networks |
Keywords:
deadlock resolution; knot; deadlock recovery; wait-for graphs; computational complexity; vertex deletion; directed feedback vertex setReferences:
| [1] | Atreya R, Mittal N, Kshemkalyani AD, Garg VK, Singhal M (2007) Efficient detection of a locally stable predicate in a distributed system. J Parallel Distrib Comput 67(4):369-385 · Zbl 1115.68028 · doi:10.1016/j.jpdc.2006.12.004 |
| [2] | Barbosa VC (1996) An introduction to distributed algorithms. The MIT Press, Cambridge |
| [3] | Barbosa, VC; Corrêa, R. (ed.); Dutra, I. (ed.); Fiallos, M. (ed.); Gomes, F. (ed.), The combinatorics of resource sharing, 27-52 (2002), Dordrecht · doi:10.1007/978-1-4757-3609-0_2 |
| [4] | Barbosa VC, Benevides MR (1998) A graph-theoretic characterization of AND-OR deadlocks. Tech. Rep. COPPE-ES-472/98, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil |
| [5] | Bokal D, Brešar B, Jerebic J (2012) A generalization of Hungarian method and Hall’s theorem with applications in wireless sensor networks. Discrete Appl Math 160(4):460-470 · Zbl 1237.05159 · doi:10.1016/j.dam.2011.11.007 |
| [6] | Bondy JA, Murty USR (1976) Graph theory with applications. North-Holland, Amsterdam · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2 |
| [7] | Bracha G, Toueg S (1987) Distributed deadlock detection. Distrib Comput 2:127-138 · Zbl 0641.68035 · doi:10.1007/BF01782773 |
| [8] | Brzezinski J, Helary JM, Raynal M, Singhal M (1995) Deadlock models and a general algorithm for distributed deadlock detection. J Parallel Distrib Comput 31:112-125 · doi:10.1006/jpdc.1995.1150 |
| [9] | Carneiro ADA, Protti F, Souza US (2017) Deletion graph problems based on deadlock resolution. In: Cao Y, Chen J (eds) Computing and combinatorics. COCOON 2017, Lecture Notes in Computer Science, vol 10392. Springer, pp 75-86 · Zbl 1434.68046 |
| [10] | Chahar P, Dalal S (2013) Deadlock resolution techniques: an overview. Int J Sci Res Publ 3(7):5p |
| [11] | Chandy KM, Lamport L (1985) Distributed snapshots: determining global states of distributed systems. ACM Trans Comput Syst 3:63-75 · doi:10.1145/214451.214456 |
| [12] | Coffman EG, Elphick M, Shoshani A (1971) System deadlocks. ACM Comput Surv (CSUR) 3(2):67-78 · Zbl 0226.68015 · doi:10.1145/356586.356588 |
| [13] | Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT Press, Cambridge · Zbl 1187.68679 |
| [14] | de Mendívil JG, Fariña F, Garitagotia JR, Alastruey CF, Bernabeu-Auban JM (1999) A distributed deadlock resolution algorithm for the AND model. IEEE Trans Parallel Distrib Syst 10(5):433-447 · doi:10.1109/71.770131 |
| [15] | Ding Y, He Y, Jiang J (2003) Multi-robot cooperation method based on the ant algorithm. In: IEEE swarm intelligence symposium, pp 14-18 |
| [16] | Galčík F, Katrenič J, Semanišin G (2011) On computing an optimal semi-matching. In: Kolman P, Kratochvíl J (eds) Graph-theoretic concepts in computer science, WG 2011, Lecture notes in computer science, vol 6986. Springer, Berlin, pp 250-261 · Zbl 1341.05207 |
| [17] | Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman and Company, New York · Zbl 0411.68039 |
| [18] | Hopcroft JE, Karp RM (1973) An \[n^{5/2}\] n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J Comput 2(4):225-231 · Zbl 0266.05114 · doi:10.1137/0202019 |
| [19] | Karp, R.; Miller, R. (ed.); Thatcher, J. (ed.); Bohlinger, J. (ed.), Reducibility among combinatorial problems, 85-103 (1972), New York · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [20] | Katrenic J, Semanišin G (2011) A generalization of Hopcroft-Karp algorithm for semi-matchings and covers in bipartite graphs. arXiv:1103.1091 |
| [21] | Kshemkalyani AD, Singhal M (1994) Efficient detection and resolution of generalized distributed deadlocks. IEEE Trans Software Eng 20:43-54 · doi:10.1109/32.263754 |
| [22] | Kshemkalyani AD, Singhal M (2011) Distributed computing: principles, algorithms, and systems. Cambridge University Press, Cambridge · Zbl 1213.68126 |
| [23] | Leung JY-T, Lai EK (1979) On minimum cost recovery from system deadlock. IEEE Trans Comput 9(C-28):671-677 · Zbl 0414.68019 · doi:10.1109/TC.1979.1675435 |
| [24] | Misra J, Chandy KM (1982) A distributed graph algorithm: Knot detection. ACM Trans Program Lang Syst 4:678-686 · Zbl 0489.68061 · doi:10.1145/69622.357190 |
| [25] | Pachl J (1997) The deadlock problem in automatic railway operation. Signal und Draht 89(1-2):22-25 |
| [26] | Pachl J (2011) Deadlock avoidance in railroad operations simulations. In: Transportation research board 90th annual meeting (paper no. 11-0175) |
| [27] | Penso LD, Protti F, Rautenbach D, dos Santos Souza U (2015) Complexity analysis of \[P_33\]-convexity problems on bounded-degree and planar graphs. Theoret Comput Sci 607:83-95 · Zbl 1332.68059 · doi:10.1016/j.tcs.2015.10.003 |
| [28] | Ryang DS, Park KH (1995) A two-level distributed detection algorithm of AND/OR deadlocks. J Parallel Distrib Comput 28:149-161 · Zbl 0939.68950 · doi:10.1006/jpdc.1995.1096 |
| [29] | Satyanarayana B, Prasad KS (2014) Discrete mathematics and graph theory. PHI Learning Pvt. Ltd, New Delhi · Zbl 1305.05001 |
| [30] | Tanenbaum AS, Woodhull AS (1987) Operating systems: design and implementation, vol 2. Prentice-Hall, Englewood Cliffs |
| [31] | Terekhov I, Camp T (1999) Time efficient deadlock resolution algorithms. Inf Process Lett 69(3):149-154 · Zbl 0917.68084 · doi:10.1016/S0020-0190(98)00203-8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
