Random Resource Allocation Graphs and the Probability of Deadlock
James Francis Lynch · SIAM Journal on Discrete Mathematics · 1994
Resource allocation graphs are directed bipartite graphs satisfying certain constraints. The two partitions of the vertex set correspond to the processes and resources of a multi-programming computer system, and the edges indicate resource allocations and requests. When all the resources are distinguishable, existence of a cycle in such a graph is equivalent to deadlock in the system. The main results here are exact and asymptotic formulas for the number of resource allocation graphs and acyclic resource allocation graphs with m processes, n allocated resources, and q edges. If a uniform probability distribution is taken on such graphs, then the proportion of blocked processes, $( q - n )/m$, determines the asymptotic behavior of the probability of deadlock: If $( q - n )/m \to 0$, then the probability of deadlock is asymptotic to 0, and if $( q - n )/m \to \alpha > 0$, then the probability is asymptotic to a positive value. Similar formulas are also given in terms of m and n only.