Revisiting deadlock prevention: a probabilistic approach. (English) Zbl 1386.05079
Summary: We revisit the deadlock-prevention problem by focusing on priority digraphs instead of the traditional wait-for digraphs. This has allowed us to formulate deadlock prevention in terms of prohibiting the occurrence of directed cycles even in the most general of wait models (the so-called AND-OR model, in which prohibiting wait-for directed cycles is generally overly restrictive). For a particular case in which the priority digraphs are somewhat simplified, we introduce a Las Vegas probabilistic mechanism for resource granting and analyze its key aspects in detail.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60C05 | Combinatorial probability |
References:
| [1] | A.Aybar and A.İftar, Deadlock avoidance controller design for timed P etri nets using stretching, IEEE Syst J2 (2008), 178-188. |
| [2] | V.C.Barbosa, An introduction to distributed algorithms, MIT Press, Cambridge, MA, 1996. |
| [3] | V.C.Barbosa, “The combinatorics of resource sharing,” Models for parallel and distributed computation: Theory, algorithmic techniques and applications, R.Corrêa (ed.), I.Dutra (ed.), M.Fiallos, and (ed.)F.Gomes (ed.) (Editors), Kluwer, Dordrecht, Netherlands, 2002, pp. 27-52. · Zbl 1046.68053 |
| [4] | G.Bracha and S.Toueg, Distributed deadlock detection, Distrib Comput2 (1987), 127-138. · Zbl 0641.68035 |
| [5] | J.Brzezinski, J.‐M.Hélary, M.Raynal, and M.Singhal, Deadlock models and a general algorithm for distributed deadlock detection, J Parallel Distrib Comput31 (1995), 112-125. |
| [6] | M.R.Garey and D.S.Johnson, Computers and intractability: A guide to the theory of NP‐completeness, Freeman, New York, 1979. · Zbl 0411.68039 |
| [7] | Z.Jin, A.K.Zaidi, and A.H.Levis, Deadlock and trap analysis in Petri nets, Technical report GMU/C3I‐158‐P, George Mason University, Fairfax, VA, 1995. |
| [8] | A.D.Kshemkalyani and M.Singhal, Efficient detection and resolution of generalized distributed deadlocks, IEEE Trans Softw Eng20 (1994), 43-54. |
| [9] | J.Misra and K.M.Chandy, A distributed graph algorithm: Knot detection, ACM Trans Program Lang Syst4 (1982), 678-686. · Zbl 0489.68061 |
| [10] | Q.Ni, W.Sun, and S.Ma, “Deadlock detection based on resource allocation graph,” Proc 5th Int Conf on Information Assurance and Security IEEE Computer Society, Los Alamitos, CA, Xi’An, China, 2009, pp. 135-138. |
| [11] | D.‐S.Ryang and K.H.Park, A two‐level distributed detection algorithm of AND/OR deadlocks, J Parallel Distrib Comput28 (1995), 149-161. · Zbl 0939.68950 |
| [12] | A.Wegrzyn, A.Karatkevich, and J.Bieganowski, Detection of deadlocks and traps in P etri nets by means of T helen’s prime implicant method, Int J Appl Math Comput Sci14 (2004), 113-121. · Zbl 1171.68581 |
| [13] | A.Yalcin and T.O.Boucher, Deadlock avoidance in flexible manufacturing systems using finite automata, IEEE Trans Robot Autom16 (2000), 424-429. |
| [14] | M.Yan, Z.Li, N.Wei, and M.Zhao, A deadlock prevention policy for a class of Petri nets S^3PMR, J Inf Sci Eng25 (2009), 167-183. |
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.
