An Efficient Algorithm for Reliability Lower Bound of Distributed Systems

Authors: Mohamed H. S. Mohamed, Yang Xiao-zong, Liu Hong-wei, Wu Zhi-bo

Abstract:

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 several typical classes of networks to evaluate the lower bounds and show the effectiveness of our algorithm.

Keywords: Distributed systems, probabilistic network, residual connectedness reliability, lower bound.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058699

References:

[1] M. O. Ball, "Complexity of network reliability computations," Networks, vol. 10, pp. 153−165, 1980.
[2] O. Frank, and W. Gaul, "On reliability in stochastic graphs," Networks, vol. 12, pp. 119−126, 1982.
[3] T. Evans, and D. Smith,"Optimally reliable graphs for both edge and vertex failures," Networks, vol. 16, pp. 199−204, 1986.
[4] F. T. Boesch, "Synthesis of reliable networks−A survey," IEEE Transactions on Reliability, vol. R−35, pp. 240−246, 1986.
[5] L. G. Valiant, "The complexity of enumeration and reliability problems," SIAM Journal of Computing, vol. 8, pp. 410−421, 1979.
[6] J. S. Provan, and M. O. Ball, "The complexity of counting cuts and computing the probability that a graph is connected," SIAM Journal of Computing, vol. 12, pp. 777−788, 1983.
[7] K. Sutner, A. Satyanarayana, and C. Suffel, "The complexity of the residual node connectedness reliability problem," SIAM Journal of Computing, vol. 20, pp. 149−155, 1991.
[8] C. J. Colbourn, A. Satyanarayana, C. Suffel, and K. Sutner, "Computing residual connectedness reliability for restricted networks," Discrete Applied Mathematics, vol. 44, pp. 221−232, 1993.
[9] Z. He, and Y. Chen, "Efficient algorithms for residual connectedness reliability of distributed systems," in Proceedings of the First International Workshop on Distributed Computing, Communication and Applications, Islamabad, Pakistan, May 2000, pp. 151−159.
[10] Z. He, Y. Tian, and Y. Chen, "Simulating the reliability of distributed systems with unreliable nodes," I. J. of Simulation, vol. 3 No. 1−2, pp. 68-79, 2002.
[11] M. R. Henzinger, S. Rao, and H. N. Gabow, "Computing vertex connectivity: new bounds from old techniques," J. of Algorithms, vol. 34 No. 2, pp. 222-250, 2000.