ABSTRACT

The reliability of distributed systems in which the communication links are considered reliable while the computing nodes may fail with certain probabilities have been modeled by a probabilistic network or a graph G. Computing the residual connectedness reliability (RCR), denoted by R(G), of probabilistic networks with unreliable nodes is very useful, but is an NP-hard problem. To derive the exact R(G) expressions for large networks can become rather complex. As network size increases, the reliability bounds could be used to estimate the reliability of the networks. In this paper, we present an efficient algorithm for computing the reliability upper bound of distributed systems with unreliable nodes. We also apply our algorithm to some typical classes of graphs in order to evaluate the upper bound and show the effectiveness and the efficiency of the new algorithm. Numerical results are presented.