An Efficient Algorithm for Reliability Lower Bound of Distributed Systems

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.

Authors:

• Mohamed H. S. Mohamed
• Yang Xiao-zong
• Liu Hong-wei
• Wu Zhi-bo

Keywords:

• Distributed systems
• probabilistic network
• residual connectedness reliability
• lower bound.

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.