Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31103
An Efficient Algorithm for Reliability Lower Bound of Distributed Systems

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


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):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1313


[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.