Fast Abstracts Archives . .

Using Multiple Variable Inversion Technique to Analyze Fault-trees with Inverse Gates

Tong Luo ¹ 

GTE Labs, Waltham, USA

 

Kishor S. Trivedi ² 

Duke University, Durham, USA

Fault trees are widely used to assess the risk of failure of systems in which safety is a critical concern. It has a concise and graphical description of the relations between component level failures and a system level undesired event. The analytical solution of a fault tree often exploits these relations thus avoiding the state explosion problem of the Markovian methods.

Fault-trees can be classified into coherent and non-coherent categories. In a coherent fault tree, logical gates are restricted to AND and OR gates [3, 6 9], and the top event is uniquely described in terms of the set of all mincuts [11]. A non-coherent fault-tree has inverse gates besides AND and OR gates. For example, it may have NOT, NAND, NOR, and XOR gates [5, 13]. The concept of mincut does not apply in this case because fault trees no longer have the monotone properties. The mincut should be replaced by prime implicant from Boolean algebra. The set of all mincuts (for coherent system) or the set of all prime implicants (for non-coherent system) can be generated by algorithms developed by Bennetts [5], or Kumamoto & Henley [12], and they capture all the modes of system failure.

Having the mincuts or prime implicants of a fault-tree, reliability can be calculated by using sum-of-disjoint-products (SDP) method. Algorithms of this kind can be classfied into single variable inversion (SVI) [7, 2, 5, 18, 1, 15, 4], and multiple variable inversion (MVI)[16, 17, 21 9, 20] categories. For coherent fault-trees, many SVI and MVI algorithms are developed, and the MVI algorithms show great advantages over the SVI algorithms because the MVI algorithms generate less disjoint products (DPs), use less storage space, and are faster, compared with SVI algorithms. For non-coherent fault-trees, only a few SVI algorithms are available, and so far no MVI algorithm is available.

We developed an MVI algorithm (we call it LT algorithm) for non-coherent fault-trees. Also we developed the E_Abraham algorithm by extending the well known Abraham's algorithm [1], which only applies to coherent fault-trees, and use the E_Abraham algorithm as a representative for SVI algorithms that can be used on non-coherent fault-trees.

Comparison of LT with the E_Abraham algorithm shows that the number of disjoint products generated by LT is always less or equal to the ones generated by the E_Abraham. For some examples, the number of disjoint products generated by LT is linear in the number of input minproducts while the number of disjoint products generated by the E_Abraham algorithm is exponential in the number of the input minproducts. Also, for these examples, the cpu time of LT is nearly linear in the number of input minproducts while the cpu time of the E_Abraham algorithm is nearly exponential in the number of the input minproducts.

In the example shown as Figure 1, for each MP_i, LT algorithm only generates 1 disjoint product while E_Abraham generates 2^i-1 disjoint products. The CPU time comparison for generating the disjoint products is shown in Figure 2.

References

[1]  J.A. Abraham. "An improved algorithm for network reliability". IEEE Transactions on Reliability, R-28:58--61, April 1979.

[2]  K. K. Aggarwal, K. B. Misra, and J. S. Gupta. "A fast algorithm far reliability evaluation". IEEE Transactions on Reliability, R-24:83--85, 1975.

[3]  R. E. Barlow and F. Proschan. Statistical theory of reliability and life testing. Holt, Rinehart and Winston, 1975.

[4]  F. Beichelt and L. Spross. "An improved abraham-method for generating disjoint sums". IEEE Transactions on Reliability, R-36:70--74, April 1987.

[5]  R. G. Bennetts. "On the analysis of fault trees". IEEE Transactions on Reliability, R-24:175--185, August 1975.

[6]  C. J. Colbourn. The combinatorics of network reliability. Oxford University Press, 1987.

[7]  L. Fratta and U. G. Montanari. "A boolean algebra method for computing the terminal reliability in a communication network". IEEE Transactions on Circuit Theory, CT-20:203--211, May 1973.

[8]  J. B. Fussell, G. J. Powers, and R. G. Bennetts. "Fault trees--a state of the art discussion". IEEE Transactions of Reliability, R-23(1), April 1974.

[9]  K. D. Heidtmann. "Smaller sum of disjoint products by subproduct inversion". IEEE Transactions on Reliability, 38:305--311, August 1989.

[10]  E. J. Henley and H. Kumamoto. Reliability engineering and risk assessment. Prentice-Hall, Englewood Cliffs, N.J., 1981.

[11]  T. Inagaki and E. J. Henley. "Probabilistic evaluation of prime implicants and top-events for non-coherent systems". IEEE Transactions on Reliability, R-29(5), December 1980.

[12]  H. Kumamoto and E. J. Henley. "Top-down algorithm for obtaining prime implicant set of non-coherent fault trees". IEEE Transaction on Reliability, R-27:242--249, October 1978.

[13]  S. A. Lapp and G. J. Powers. "Computer-aided synthesis of fault trees". IEEE Transactions on Reliability, R-26:2--13, April 1977.

[14]  W. S. Lee, D. L. Grosh, F. A. Tillman, and C. H. Lie. "Fault tree analysis, methods, and applications -- a review". IEEE Transactions on Reliability, R-34(3):194--203, August 1985.

[15]  M. O. Locks. "A minimizing algorithm for sum of disjoint products". IEEE Transactions on Reliability, R-36(4):445--453, October 1987.

[16]  T. Luo and K. S. Trivedi. "An improved algorithm for coherent system reliability". IEEE Transactions on Reliability, 47(1):73--78, March 1998.

[17]  T. Luo and K. S. Trivedi. "An improved multiple variable inversion algorithm for reliability calculation". In Proceedings of the 10th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation, pages 180--193, Palma de Mallorca, Spain, September 1998. Universitat de las Illes Baleas.

[18]  S. Rai and K. K. Aggarwal. "An efficient method for reliability evaluation of a general network". IEEE Transactions on Reliability, R-27:206--211, August 1978.

[19]  D. R. Shier. Network reliability and algebraic structures. Oxford University Press, Oxford, 1991.

[20]  S. Soh and Rai. "Carel: computer aided reliability evaluator for distributed computing networks". IEEE Transactions on Parallel and Distributed Systems, pages 199--213, April 1991.

[21]  M. Veeraraghavan and K. S. Trivedi. "An improved algorithm for symbolic reliability analysis". IEEE Transactions on Reliability, 40:347--358, August 1991.

2.  Author contact: Dept. of Electrical Engineering,
Duke University, Durham NC 27708, USA.
Phone: 919-660-5269. Fax: 919-660-5293. E-Mail: kst@ee.duke.edu