FTA: Algorithms


There are many algorithms developed for fault tree analysis since the 1960s, but MOCUS-based and BDD-based algorithms are most used in current PRA software [Rau93] [Rau03]. More information can be found in References.


MOCUS is a top-down algorithm first proposed by J.Fussel and W.Vesely in 1972. There are many suggested improvement techniques for this algorithm, but the basics are simpler than for other FTA algorithms [Rau03]. In addition, MOCUS-like algorithms may incorporate approximations to speed up their calculations; however, this may lead to inaccuracies in overall analysis. There seem not to be overall consensus on these approximations over all the tools that use this algorithm. The MOCUS algorithm is used by many FTA tools, such as RiskSpectrum and SAPHIRE.

Binary Decision Diagram

The BDD-based algorithm can use various types of the Binary Decision Diagram ([BDD], [ZBDD]) for Boolean operations [Bry86] [Min93] [Rau93]. This is a bottom-up approach that is mature and well tuned for PRA and other logic applications. This method consists of many complex algorithms of the BDD to find MCS [Rau01]. The BDD algorithms tend to be faster than MOCUS and other algorithms; however, this algorithm is subject to combinatorial explosion for very large models with thousands of basic events and gates with many replicated events. One more important advantage of the BDD-based analysis is that the BDD allows fast and exact calculation of probabilities, which makes Probability, Importance, Uncertainty analyses fast as well [DR01]. This algorithm is used in CAFTA, RiskA, and RiskMan.

Prime Implicants vs. Minimal Cut Sets

Minimal cut sets are necessary and sufficient sets of basic events (variables) that induce the failure of the top event [Rau01]. The set represents a conjunction of Boolean variables (product). Another way to represent the minimal sets of basic events is to consider the shortest paths for top event failure. If one path includes another, it is not the shortest so is not minimal.

The notion of minimal cut sets with occurrence or failure of basic events is appropriate for coherent fault trees. For non-coherent fault trees with complements of basic events, success or non-occurrence of basic events may lead to the failure of the top event. In order to capture these scenarios, prime implicants are computed as products that include complements of variables.

However, the notion of prime implicants may not be as intuitive as the notion of minimal cut sets for analysts since consideration of success of an undesired event complicates failure scenarios or may be irrelevant at all if the probability of success is close to 1.

Minimal cut sets can be used as a conservative, approximate result for analysis of non-coherent fault trees. In order to eliminate complements of variables, it is assumed that a complement of an event always occurs, i.e., constant True or 1, unless the complement is in the same path or set as the corresponding event. In the latter case, the path or set is Null or an impossible scenario because an event and its complement are mutually exclusive.

This approximation is conservative because the worst case scenario is considered for complements. Moreover, the computation of minimal cut sets is simpler than the computation of prime implicants. Calculation of prime implicants involves extra computations in accordance to the Consensus theorem and generates a lot more products than calculation of minimal cut sets [PA09].

The benefit of calculation of prime implicants is that it is the exact representation of the system without approximations. Computation of prime implicants is necessary if complements or success of events cannot or should not be ignored. Relevancy notion is given to events depending on the membership in products. If an event is in a product as a positive literal, the event is failure relevant. If an event is in a product as a negative literal (complement of the event), the event is repair (success) relevant. If an event is not in a product, it is irrelevant.

Given Boolean formula \(f(a,b,c)\):

\[f(a,b,c) = a \& b \| \overline{a} \& c\]

Considering the complement is always True, the formula is simplified:

\[f(a,b,c) = a \& b \| c\]

Computation of prime implicants requires computation of the consensus when variable \(a\) is irrelevant:

\[f(a,b,c) = a \& b \| \overline{a} \& c \| b \& c\]

Minimal cut sets of the formula are \({ab, c}\). Prime implicants are \({ab, \overline{a}c, bc}\).

SCRAM FTA Algorithms


This algorithm is similar to the MOCUS algorithm as described in [Rau03]. Steps in the algorithm for minimal cut set generation from a fault tree.

Rule 1. Each OR gate generates new rows (sets) in the table (set) of cut sets

Rule 2. Each AND gate generates new columns (elements) in the table (set) of cut sets

After finishing or each of the above steps:

Rule 3. Eliminate redundant elements that appear multiple times in a cut set

Rule 4. Eliminate non-minimal cut sets

The implementation uses a ZBDD data structure (a set of sets) to store minimal cut sets in a compact form, so Rules 3 and 4 are satisfied automatically. Elements in a set have AND relationship with each other; whereas sets in the ZBDD have OR relationship with each other.

Gates of top and intermediate events affect cut sets. Each OR gate adds new sets into the set of sets, while each AND gate adds additional elements into one specific set or group of sets inside the set of sets.

To generate all cut sets, a fault tree is traversed from the top to basic events, In this step, the analysis may cancel cut sets if the fault tree is non-coherent and contains complements. In addition, if a cut set order is larger than the limit put by a user, it is discarded.

After required cut sets are generated, the minimization of the generated cut sets and extraction of minimal cut sets into a final (result) form is delegated to ZBDD facilities.

Binary Decision Diagram

Binary decision diagrams are constructed from PDAGs for analysis. In order to calculate minimal cut sets or prime implicants, BDD is converted into Zero-suppressed binary decision diagrams (ZBDD). ZBDD is a data structure that encodes sets in a compact way [Min93]. Minimization of sets is performed with subsume operations described in [Rau93]. After these operations, any path leading to 1 (True) terminal is extracted as a product.

Zero-Suppressed Binary Decision Diagram

In addition to being a helpful facility for set minimization, ZBDDs can work directly with PDAGs [Jun09]. The major benefit of this approach is that products can be kept minimal and truncated upon generation. However, the application of Boolean operators on the ZBDD decomposition requires extra computations compared to the BDD approach.

Product Container

All the FTA algorithms in SCRAM produce ZBDD as a result of analysis to encode the sum of products. An alternative representation, for example, would be an array (of sets, bitsets, arrays, etc.), which is a very general data structure providing a flexible interface and standard algorithms (sort, partition, query, iteration, etc.); however, this kind of alternatives is not as space and time efficient as ZBDD. Moreover, there’s great overhead in converting the resultant ZBDD into some other data structures. For these performance reasons, other analysis and post-processing facilities utilize or are expected to work with the ZBDD representation directly.

UNITY and NULL Cases

The analyzed products may result in NULL (empty) or UNITY (base) sets, which may indicate guaranteed success or failure. These cases are handled as special and given appropriate messages and probabilities. UNITY (base) set shows only one empty product of order 1 and probability 1. NULL (empty) set has probability 0 and shows no products.