Bounds on the Reliability of Distributed Systems With Unreliable Nodes & Links

The reliability of distributed systems & computer networks in which computing nodes and/or communication links may fail with certain probabilities have been modeled by a probabilistic network. Computing the residual connectedness reliability (RCR) of probabilistic networks under the fault model with both node & link faults is very useful, but is an NP-hard problem. Up to now, there has been little research done under this fault model. There are neither accurate solutions nor heuristic algorithms for computing the RCR. In our recent research, we challenged the problem, and found efficient algorithms for the upper & lower bounds on RCR. We also demonstrated that the difference between our upper & lower bounds gradually tends to zero for large networks, and are very close to zero for small networks. These results were used in our dependable distributed system project to find a near-optimal subset of nodes to host the replicas of a critical task.