Complexity of Network Reliability and Optimal Resource Placement Problems
Donald Barton Johnson, Larry Raab · SIAM Journal on Computing · 1994
A fundamental problem of distributed system design in an existing network where components can fail is finding an optimal location at which to place a resource. This paper proves exactly how hard this placement problem is under the measure of data availability. Specifically, it shows that the optimal placement problem for availability is #P-complete, a measure of intractability at least as severe as $NP$-completeness. To obtain these results, the environment in which a distributed system operates is modelled by a probabilistic graph, which is a set of fully reliable vertices representing sites and a set of edges representing communication links, each operational with a rational probability. Finding the optimal placement in a probabilistic graph is proved to be #P-complete by giving a sequence of Turing reductions from #Satisfiability. This result is generalized to networks in which each site and each link has an independent, rational operational probability and to networks in which all the sites or all the links have fixed, uniform operational probabilities. Given the anticipated computational difficulty of finding an exact solution, the requirements for effective, practical approximation methods are discussed.