Home / Guides / MOCUS vs BDD — when each wins

Algorithms · Comparative

MOCUS vs BDD — when each algorithm wins

Every fault-tree tool uses one of two algorithms to compute the answer: MOCUS, a top-down substitution method that produces the minimal cut sets directly, or Binary Decision Diagrams (BDD), a Boolean-function representation that gives an exact top-event probability without enumerating cut sets at all. They scale very differently — for small trees you'll never notice; for industrial PRAs, picking the wrong one is the difference between a five-second analysis and one that doesn't terminate. This guide explains how each works, where each wins, and how to recognise which regime your tree is in.

≈ 17 min read Worked tree: rail / SPAD (Article 1) References: IEC 61025, NRC PRA tools (SAPHIRE, Riskman)

Why this matters in practice

For the eight-event SPAD tree from Article 1, MOCUS finishes in microseconds and BDD finishes in microseconds. Either one is fine. But fault trees in industrial use look nothing like the SPAD tree: a typical nuclear PRA has 50,000+ basic events, deep gate hierarchies with significant sharing of subsystems, and mission-time-window logic that explodes the cut-set count into the millions. Three things change at scale:

Cut-set count explodes faster than you think. An OR of N independent ORs of M events each has N×M cut sets — linear, easy. An AND of N ORs of M events each has M^N cut sets — exponential, fatal. Real systems are full of the second pattern (any redundancy is structurally an AND of OR), and MOCUS enumerates each one.
Cut-set truncation introduces error. Most real MOCUS implementations stop expanding cuts once their probability drops below a threshold (e.g. 10⁻¹²). The truncated cuts become invisible to the rest of the analysis — including importance measures. BDD doesn't truncate; it computes the exact P(TOP) regardless of cut-set count.
Disjoint events and NOT gates break MOCUS's assumptions. The classical MOCUS algorithm assumes coherent fault trees (no NOTs, no XORs, no INHIBIT gates resolving to negation). The moment you add disjoint groups for mutually exclusive events — or an XOR for exactly-one-of — the rare-event approximation that lets MOCUS sum cut probabilities stops being correct, and the corrections are non-trivial. BDD handles non-coherent trees without modification.

The practical question isn't "which algorithm is better" — neither dominates the other across all inputs. It's "given my tree, which one finishes faster, gives a more defensible answer, and supports the importance measures my standard requires?". The answer changes with tree size, tree shape, and the presence of non-coherent gates. Working through how each algorithm operates, in order, is the fastest path to that judgement.

Step 1How MOCUS works

MOCUS — Method for Obtaining Cut Sets — was published by Fussell and Vesely in 1972 and is still the dominant cut-set algorithm in commercial FTA tools (FaultTree+, Reliability Workbench, FTA Studio's own implementation). It is a deductive top-down substitution. Starting from the top event, replace every gate with its children and apply two Boolean rewrites until no gate remains:

Distribute AND over OR. If you reach an AND of two ORs, the result is the OR of the four pairwise ANDs. (A ∨ B) ∧ (C ∨ D) → (AC) ∨ (AD) ∨ (BC) ∨ (BD).
Apply absorption. Whenever a candidate cut contains another candidate cut, the larger one is redundant. {A, B, C} ∪ {A, B} → {A, B}. This is what guarantees the output is the set of minimal cut sets, not the (much larger) set of all cut sets.

Walked through on the SPAD tree (which Article 1 already developed), the substitution looks like:

TOP = G-001 ∨ G-002 ∨ G-005
    = (BE-001 ∨ BE-002 ∨ BE-003)              [expand G-001, OR]
      ∨ (G-003 ∧ G-004)                       [expand G-002, AND]
      ∨ (BE-008 ∧ BE-009)                     [expand G-005, AND]

    = BE-001 ∨ BE-002 ∨ BE-003
      ∨ ((BE-004 ∨ BE-005) ∧ (BE-006 ∨ BE-007))
      ∨ (BE-008 ∧ BE-009)

    = BE-001 ∨ BE-002 ∨ BE-003
      ∨ (BE-004·BE-006) ∨ (BE-004·BE-007)     [distribute AND over OR]
      ∨ (BE-005·BE-006) ∨ (BE-005·BE-007)
      ∨ (BE-008·BE-009)

Eight cut sets, no absorption needed (no cut is a superset of another). MOCUS terminates in two substitution passes for this tree.

The cost-of-MOCUS story is in the AND distribution. Two ORs combined under an AND multiply their child counts. An AND of three independent 3-event ORs becomes 27 cut sets; an AND of four 4-event ORs becomes 256; an AND of six 5-event ORs becomes 15,625. These trees are not pathological — they're what you get when modelling a 6-out-of-N voting system, or four parallel safety functions each with five contributing failure modes. Industrial PRA models routinely produce 10⁶ to 10⁸ cut sets before truncation.

The truncation knob — and what it costs you Every production MOCUS implementation has a probability cut-off (commonly 10⁻¹²): if a candidate cut's probability falls below the threshold during expansion, the cut is dropped and the algorithm proceeds. This keeps memory bounded but makes every downstream metric — P(TOP), F-V importance, RAW, RRW — an under-estimate by an unknown amount. In a high-safety-stakes submission you have to defend the choice of truncation level by re-running at progressively lower thresholds and showing convergence. BDD doesn't have this problem because it never enumerates cuts in the first place.

Step 2How BDD works

Binary Decision Diagrams were introduced by Randal Bryant in 1986 as a canonical representation of Boolean functions. Coudert and Madre adapted them to FTA in 1992, and Rauzy's 1993 work on Reduced Ordered BDDs made them the dominant algorithm in modern PRA software (SAPHIRE, Riskman, RiskA). Where MOCUS hands you a list of cut sets and asks you to sum them, BDD hands you a Boolean function in a form that lets you compute P(TOP) directly, without ever enumerating cuts at all.

Shannon decomposition — the one trick

Every BDD operation is built on one identity, called Shannon decomposition: any Boolean function f(x₁, …, x_n) can be split on any variable as

f = x_i · f|_{x_i=1} + ¬x_i · f|_{x_i=0}

where f|_{x_i=1} is the function with x_i replaced by true (the "1-cofactor") and similarly for the 0-cofactor. Recursively applying this rule with a fixed variable order produces a directed acyclic graph: an interior node per variable encountered, two children (the 1-cofactor and 0-cofactor sub-BDDs), and two terminals (constants 0 and 1). The reduction rules are simple — eliminate any node whose children are identical, and share any two isomorphic subgraphs — and they produce a canonical form: two Boolean functions are equal iff their reduced ordered BDDs are isomorphic.

Worked example — the SPAD ATP branch

Take just the ATP gate G-002 from Article 1: (BE-004 ∨ BE-005) ∧ (BE-006 ∨ BE-007). Pick a variable ordering — say BE-004 < BE-005 < BE-006 < BE-007 — and decompose:

G-002 = BE-004 · (G-002|_BE-004=1) + ¬BE-004 · (G-002|_BE-004=0)

  G-002|_BE-004=1 = (1 ∨ BE-005) ∧ (BE-006 ∨ BE-007)
                = BE-006 ∨ BE-007

  G-002|_BE-004=0 = (0 ∨ BE-005) ∧ (BE-006 ∨ BE-007)
                = BE-005 ∧ (BE-006 ∨ BE-007)

The subgraph BE-006 ∨ BE-007 appears in both branches — the BDD shares it as a single node, no duplication. The full BDD has four interior nodes (one per variable) plus the 0 and 1 terminals — four nodes for four variables, the floor for this function.

To get P(G-002), walk the BDD in one pass, applying the recurrence at each interior node:

P(node v) = P(var(v)) · P(high-child of v) + (1 − P(var(v))) · P(low-child of v)

Plugging in the SPAD probabilities (BE-004 = 4.37×10⁻³, BE-005 = 2.62×10⁻³, BE-006 = 1.75×10⁻³, BE-007 = 8.76×10⁻⁴):

P(BE-006 ∨ BE-007) = 0.00175 + 0.000876 − (0.00175 × 0.000876)
                   ≈ 2.624×10⁻³

P(BE-005 ∧ (BE-006 ∨ BE-007)) = 0.002624 × 0.002624 ≈ 6.88×10⁻⁶

P(G-002) = P(BE-004) × P(BE-006 ∨ BE-007)
         + (1 − P(BE-004)) × P(BE-005 ∧ (BE-006 ∨ BE-007))
       ≈ 0.00437 × 0.002624 + 0.99563 × 6.88×10⁻⁶
       ≈ 1.146×10⁻⁵ + 6.85×10⁻⁶
       ≈ 1.83×10⁻⁵

This is the exact probability — every inclusion-exclusion term is captured by the recurrence. Compare to the MOCUS rare-event approximation from Article 1, which summed the four ATP cut sets as 7.65 + 3.83 + 4.59 + 2.30 ×10⁻⁶ = 1.84×10⁻⁵. Same answer to three significant figures, because in this regime the inclusion-exclusion corrections are negligible. The point isn't that BDD gave a different answer here — it's that BDD's answer is structurally exact for any tree, while MOCUS's depends on probabilities being small enough for rare-event to apply.

Variable ordering — where BDD lives or dies

The Shannon decomposition is correct under any variable order, but BDD size can vary by orders of magnitude across orderings. The classical example (Bryant 1986) is the function x₁x₂ + x₃x₄ + … + x_2n−1x_2n:

Good order (x₁, x₂, x₃, x₄, …): BDD size O(n).
Bad order (x₁, x₃, …, x_2n−1, x₂, x₄, …): BDD size O(2ⁿ).

Finding the optimal ordering is NP-hard, but cheap heuristics get within a small constant of optimal for fault trees in practice. The standard heuristics — DFS, topological, weight-based — exploit the fact that fault trees have local sub-structures (a subsystem appears in several places), and putting the variables of the same sub-structure close together in the order keeps the BDD small. Most production tools choose the order automatically; some let you override.

Why MOCUS users sometimes mistake BDD for "the same thing in different clothes" The two algorithms produce identical answers on small or sparse trees because the inclusion-exclusion terms are small and the cut-set count is manageable. The divergence appears at scale — at 10⁵ basic events with significant subsystem sharing, MOCUS produces 10⁷ candidate cuts (most of which it truncates) and BDD produces a 10⁵-node graph. They are not the same algorithm in different clothes; they have different complexity laws, and at scale the difference decides whether the analysis terminates.

Step 3The complexity story — what scales how

Both algorithms are exponential in the worst case (MOCUS in number of cut sets; BDD in graph size under bad orderings), but the worst case rarely hits because real fault trees have structure. The practical question is the typical case for a given tree size and shape. Approximate ranges for what each algorithm produces on representative inputs:

Tree	Events	Cut sets (after truncation)	MOCUS time	BDD time (good order)
SPAD (this article)	9	8	< 1 ms	< 1 ms
Typical safety subsystem	~50	~10³	~10 ms	~10 ms
ARP 4761 SSA module	~500	~10⁵	~1 s	~100 ms
NRC PRA system fault tree	~5,000	~10⁷ (truncated)	~10 s with truncation	~1 s
Full-plant PRA	~50,000	≥10⁸ (truncated)	minutes–hours, truncated	seconds–minutes

Rough industry ranges, not benchmarks — actual numbers depend on tool, hardware, and the tree's specific structure. The shape of the table matters more than the absolute numbers: at the small end, the algorithms are interchangeable; in the middle, BDD is faster and exact while MOCUS is faster to interpret; at the top, MOCUS only completes by truncating.

Two structural drivers explain the curve:

Subsystem sharing. A bus, a power supply, an HVAC unit appearing in dozens of failure paths blows up the cut-set count under MOCUS (each appearance distributes through ANDs above it) but is cheap for BDD (one variable, one node, shared by every reference). Modern PRAs are full of shared subsystems — that's why BDD became dominant in nuclear PRA in the 1990s.
Non-coherent gates. XOR, NOT, INHIBIT-with-negation, disjoint event groups — anything that introduces complementation. MOCUS's algebra was designed for coherent trees; non-coherence forces either a workaround (signed cut sets, with manual inclusion-exclusion bookkeeping) or a fundamentally different algorithm. BDD just handles them, because the Shannon decomposition doesn't care about gate semantics.

One caveat about the BDD column: "good order" is doing a lot of work in those numbers. A bad variable ordering can blow a 10⁵-node BDD up to 10⁹ nodes — at which point BDD becomes worse than MOCUS, not better. Production PRA tools spend substantial effort on ordering heuristics for this reason; some let you re-run with a different heuristic if the first doesn't terminate.

Step 4Choose the algorithm that matches your tree

Translating the complexity story into a decision rule:

Your tree	Choose	Why
Hand-built, < 100 basic events, coherent — typical safety case for an automotive ECU, a medical device, a single rail signal, a small-process IPL stack.	MOCUS	Cut sets are the deliverable for design review. Reviewers want to see "this single failure causes the top event" or "these two failures must coincide" expressed as a list, and MOCUS produces that list as its primary output. BDD is fine here too, but its output then needs converting to cut sets for the conversation.
100–1,000 events, redundant subsystems — aerospace SSA module, rail signalling subsystem, process plant IPL with shared-utility ICs.	BDD	This is the regime where MOCUS truncation starts costing accuracy and BDD's exactness matters for defensibility. Importance measures still come out cleanly (computed via cofactor differences); cut sets are still extractable from the BDD if needed.
1,000+ events, deep subsystem sharing — full-system PRA, a complete nuclear-island model, an aircraft-level functional hazard assessment.	BDD (essential)	MOCUS without truncation may not finish; with truncation, the answer's accuracy depends on a knob whose correct setting is itself a quantification problem. BDD with a decent variable ordering produces an exact answer in a bounded time.
Any tree with NOT, XOR, or disjoint-event groups — typical of cybersecurity FTAs, dynamic systems modelling, or systems where success and failure share components.	BDD (essential)	MOCUS cannot quantify non-coherent trees correctly without a workaround that's itself error-prone. BDD handles them natively because Shannon decomposition is gate-agnostic.
Cut sets are the regulator's deliverable — e.g. NRC PRA single-cut-set reports, EN 50126 SIL apportionment by cut set, ARP 4761 single-failure justifications.	MOCUS or hybrid	The regulator wants the cut-set list. If your tool runs BDD internally for quantification but extracts cut sets from the BDD for reporting, that's fine — the dominant tools (SAPHIRE, RiskSpectrum) work this way. Pure MOCUS is also fine here.
You need uncertainty bands — a Monte Carlo wrapper around the analysis.	Either — but BDD is faster per sample	Monte Carlo varies leaf probabilities and re-quantifies. Per-sample, MOCUS is doing the same enumeration repeatedly (with caching this is cheap); BDD rebuilds nothing structural and just re-walks the graph with new probabilities (usually faster). For 10⁵+ samples on a moderate tree, BDD's per-sample speed advantage compounds.

What about FTA Studio? The toolchain uses MOCUS to enumerate cut sets (so the cut-set list is always available for review and export to IEC 61025-format JSON), then exact Boolean evaluation for P(TOP) — equivalent in result to a BDD walk for the trees that fit our resolution band. A pure-BDD path would let us scale to PRA-sized models, and is on the roadmap; the engineering call we made was that small-to-medium trees are 95% of the use case and MOCUS-with-exact-eval has the better explainability story for the design-review conversation.

The pragmatic shortcut If your tree has fewer than a few hundred events and is coherent, use whichever your tool defaults to — both will finish quickly with the same answer. The choice only starts mattering when you cross into PRA territory or non-coherent gates. At that point, treat MOCUS truncation level as a parameter you have to defend, and BDD variable ordering as a question to ask your tool's documentation before trusting the answer.

Operational notes a reviewer will ask about

Beyond which algorithm to choose, four operational questions show up in submissions where MOCUS or BDD has been used. Each is the kind of thing a reviewer will probe, and being able to answer ahead of being asked is most of the work.

Cross-validation between the two algorithms. If your tool supports both, run both on the same tree and compare. Agreement to four or five significant figures is reassurance; a discrepancy of more than 1% flags one of two specific problems — MOCUS truncation set too aggressively, or BDD memory hitting a ceiling and silently giving up. Both fail modes are real; published PRA tool comparisons (the OpenPSA benchmark suite, EDF's RiskSpectrum vs SAPHIRE work) routinely catch them this way.
Common-cause failure groups. CCF interacts differently with the two algorithms but neither handles it implicitly — you have to declare the CCF groups explicitly. MOCUS expands a β-factor common-cause as a basic event that appears in every cut its component would have appeared in (cut-set count grows). BDD adds the CCF as a node in the variable ordering with shared-fan-out (graph size grows modestly). Either way, undeclared common-cause failures invalidate the answer; model them explicitly.
Importance-measure parity. F-V importance computed from MOCUS cut-set sums and F-V computed from BDD cofactor differences should agree. They do, exactly, until truncation kicks in — at which point MOCUS-derived importance values are biased low by the same factor as the truncated cuts. If your importance ranking is being used to justify design decisions, the truncation level used to compute it has to be defensibly tight (typically < P(TOP) / 10³).
Tool versioning. PRA submissions document the tool name and version because MOCUS and BDD implementations have known boundary-case bugs — pathological trees that produce wrong answers in tool X version Y. Reviewers expect tool-version pinning, and any change of tool or version mid-project triggers a re-validation conversation. The same hygiene matters at smaller scales too, just less visibly.

Where to go next

Run MOCUS on your own tree. Open FTA Studio — every fault tree gets a cut-set table and quantitative analysis automatically. The MOCUS implementation is the one used to derive the eight cut sets in Article 1.
Read the importance-measures guide if you haven't. Article 2 walks through how the four importance measures are computed once you have cut sets in hand — the natural next step after either algorithm finishes.
For PRA-scale models, NRC's SAPHIRE and Lloyd's Register's RiskSpectrum are the dominant BDD-based commercial tools. Both produce outputs FTA Studio can consume via the IEC 61025 JSON interchange format, so cross-validation between a small-tree MOCUS run and a large-tree BDD run is supported.
For non-coherent trees, the OpenPSA model exchange format (XFTA) is the relevant interchange standard; both FTA Studio and the major commercial tools read it.

MOCUS vs BDD — when each algorithm wins

Why this matters in practice

Step 1How MOCUS works

Step 2How BDD works

Shannon decomposition — the one trick

Worked example — the SPAD ATP branch

Variable ordering — where BDD lives or dies

Step 3The complexity story — what scales how

Step 4Choose the algorithm that matches your tree

Operational notes a reviewer will ask about

Where to go next

Continue