An efficient lower bound for the residual connectedness reliability of distributed systems

This paper discusses the reliability of distributed systems in which nodes may fail with certain probabilities while the edges are considered reliable. The reliability of distributed systems and computer networks have been modeled by a probabilistic network or a graph G. Computing the residual connectedness reliability (RCR), denoted by R (G), under the node fault model is very useful, but is an NP-hard problem. Since it may need exponential time of the network size to compute the exact value of R (G), it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. In this paper, we propose an efficient algorithm for reliability lower bound of distributed systems with unreliable nodes. We also applied our algorithm to some networks to evaluate the lower bounds and show the effectiveness of our algorithm.