🤖 AI

Actual causality in fault trees

This paper applies Halpern & Pearl's theory of actual causality to fault trees, providing a complete classification of causal notions based on the trees' structural and logical properties to enable effective failure diagnostics by linking minimal cut sets to actual causes.

Original authors: Georgiana Caltais, Milan Lopuhaä-Zwakenberg, Mariëlle Stoelinga

Published 2026-07-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Georgiana Caltais, Milan Lopuhaä-Zwakenberg, Mariëlle Stoelinga

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Why did the system break?

This paper is about a specific type of detective work used in engineering and safety systems. The authors are taking a tool called a Fault Tree (which engineers use to predict what could go wrong) and upgrading it to answer why it actually went wrong in a specific situation.

Here is the breakdown using simple analogies.

1. The Setup: The "Fish Doorbell"

The paper uses a real-world example called the "Fish Doorbell" in Utrecht, Netherlands.

The Goal: A lock needs to open to let fish swim through a canal.
The Problem: The lock failed to open.
The System: To open the lock, you need electricity. If the electricity is out, the lock stays shut. But there's a backup: If the electricity is fine, a human (the operator) or the public (watching a camera) can ring a "doorbell" to open it. However, both the public and the operator must fail to act for the backup to fail.

Engineers draw this as a Fault Tree (a flowchart of logic). It looks like a family tree of failures:

Top: The Lock Fails.
Branches: It fails if (Electricity Fails) OR if (The Alert Fails).
Sub-branches: The Alert Fails only if (Public Fails) AND (Operator Fails).

2. The Old Way vs. The New Way

The Old Way (Minimal Cut Sets):
Traditionally, engineers look at the tree to find "Minimal Cut Sets." Think of these as the smallest groups of ingredients needed to bake a bad cake.

Recipe A: Electricity fails. (That's enough to ruin the cake).
Recipe B: Public fails AND Operator fails. (Both are needed to ruin the cake).
The Limitation: This tells you what combinations could cause a disaster, but it doesn't tell you which specific ingredient caused the disaster today.

The New Way (Actual Causality):
The authors ask: "Okay, the cake is burnt. Who is actually to blame?"
They use a theory called Halpern & Pearl's Actual Causality. This is like a counterfactual test: "If we had fixed just this one thing, would the cake still be burnt?"

If the electricity was fine, but the public and operator both ignored the fish, then both are to blame.
If the electricity was dead, it doesn't matter if the public was lazy; the electricity is the sole cause.

3. The Three Types of "Blame"

The paper classifies "blame" into three different flavors, depending on how strictly you look at the system's structure:

Flavor 1 (AC-o): The "Strict Path" Blame.
This looks at the specific path the failure took. It asks: "Was there a clear, unbroken line of 'Yes, this failed' from the bottom of the tree to the top?"
- Analogy: If a domino falls, it must have been pushed by the one before it. If there's a gap in the line of falling dominos, the first one isn't the cause.
- Result: Usually, only one specific event is the "actual cause" under this strict view.
Flavor 2 (AC-u): The "Updated" Blame.
This is a slightly more flexible version. It asks: "Even if we fix other things that didn't happen, would this specific failure still have caused the problem?"
- Analogy: Imagine a car crash. If the driver was speeding, but the brakes were also bad (even though they didn't fail this time), the updated view checks if the speeding alone was enough to cause the crash regardless of the brakes.
- Result: Like the first flavor, this usually points to a single event as the cause in these specific trees.
Flavor 3 (AC-m): The "Modified" Blame.
This ignores the specific shape of the tree and looks only at the logic (the math). It asks: "If we remove this specific failure, does the system work again?"
- Analogy: This is like looking at the recipe. If you remove "Salt" and the cake is still ruined, Salt wasn't the cause. If you remove "Eggs" and the cake is saved, Eggs were the cause.
- Result: This can blame groups of things. For example, "The Public AND the Operator" together are the cause, even if neither alone would have done it.

4. The Big Surprise: The Shape Matters

The paper found something very interesting: Two systems can have the exact same "recipe" (logic) but different "shapes" (structure), and they will blame different things.

The Analogy: Imagine two bridges.
- Bridge A: Has a single weak bolt. If it breaks, the bridge falls.
- Bridge B: Has the same single weak bolt, but it's connected to a redundant support beam that also has a weak bolt.
- Even if the math says they are equally likely to fail, the structure of the second bridge changes who we blame. In the first bridge, the bolt is the cause. In the second, the "system design" might be the cause.
The Takeaway: You can't just look at the math of the failure; you have to look at how the parts are connected.

5. The Detective Work (Algorithms)

The authors didn't just talk about theory; they wrote algorithms (step-by-step instructions for computers) to find these causes.

For the "Strict" and "Modified" flavors, they found efficient ways to solve the puzzle.
For the "Updated" flavor, they found it's much harder (like trying to solve a maze with a million paths), and they admit they need more work to make it faster.

Summary

This paper takes a standard engineering tool (Fault Trees) and upgrades it with a sophisticated "blame game" theory.

It translates the tree into a logic puzzle.
It defines three ways to assign blame (Strict, Updated, Modified).
It proves that the shape of the system matters just as much as the logic.
It provides a recipe (algorithm) for computers to automatically find the "guilty" parts of a system after a failure.

The goal isn't just to say "The system failed," but to say exactly why it failed in a way that helps engineers fix the specific problem, rather than just guessing.

Technical Summary: Actual Causality in Fault Trees

Problem Statement

Fault trees (FTs) are a standard, hierarchical tool for analyzing system reliability and risk, primarily used to answer "what can go wrong?" through Minimal Cut Set (MCS) analysis. MCSs identify sets of basic events (BEs) that, if they occur simultaneously, cause system failure. However, FTs lack a formal framework to answer the diagnostic question "why has it gone wrong?" after a specific failure event has occurred. While the Halpern & Pearl (H&P) framework of Actual Causality (AC) provides a rigorous method for determining causes in complex systems using counterfactuals and interventions, its systematic application to Fault Trees is currently missing from the literature. Existing connections between AC and FTs are limited to generating trees from trace data or translating attack trees to causal models without investigating the actual causes within the tree structure.

Methodology

The authors bridge this gap by formally translating Fault Trees into Causal Models (CMs) compatible with the H&P framework.

Translation to Causal Models: The paper defines a mapping where every node in a Fault Tree (Basic Events, AND-gates, OR-gates) becomes an endogenous variable in a Causal Model. Basic Events are associated with exogenous variables representing the context (the status vector). The logical structure of the FT (AND/OR gates) is preserved as structural equations in the CM.
Application of AC Definitions: The authors apply three specific definitions of actual causality from the H&P literature to these translated models:
- AC-o (Original): The standard definition requiring a partition of variables and counterfactual tests.
- AC-u (Updated): A refinement addressing cases where causes are redundant or partial.
- AC-m (Modified): A simplified definition focusing on the actual context values rather than hypothetical contingencies.
Classification and Analysis: The authors derive necessary and sufficient conditions for a variable (or set of variables) to be an actual cause of the top-level event failure ( $X_{Root}=1$ ) under each definition. They analyze these conditions in terms of the FT's graph structure (paths, gate types) and its logical structure (Boolean functions).
Complexity and Algorithms: The paper analyzes the computational complexity of determining actual causes for each definition and proposes algorithms to compute them.

Key Contributions and Results

1. Classification of Actual Causality in FTs

The paper provides complete classifications for AC-o, AC-u, and AC-m specifically for Fault Trees:

AC-o and AC-u: Both definitions result in singleton causes (a single event) in FTs. A variable $X_v=1$ $X_{v} = 1$ is an actual cause if there exists a path from $v$ $v$ to the root where all nodes evaluate to 1, subject to specific constraints regarding shared inputs between AND and OR gates.
- Key Finding: Equivalent FTs (those with identical structure functions) can yield different actual causes under AC-o and AC-u. This is because AC definitions treat intermediate gates as real-world events subject to intervention, not just logical functions.
- Distinction: AC-u adds a condition requiring that setting the children of OR-gates on the path to 0 (via intervention) does not prevent the root from failing, provided the context is maintained.
AC-m: This definition behaves differently, relying purely on the Boolean structure function rather than the graph topology. A set of Basic Events $C$ is an actual cause under AC-m if and only if $C$ is a Minimal Path Set of the "positive part" of the FT (the sub-tree containing only events that occurred). This establishes a direct link between AC-m and the concept of Minimal Path Sets (the dual of MCSs).

2. Relationship Between Minimal Cut Sets (MCS) and Actual Causes

The authors clarify the relationship between the traditional FT concept of MCSs and Actual Causality:

Necessary but not Sufficient: Being part of an MCS is not sufficient to be an actual cause in a specific context.
Sufficient Condition: If an MCS $C$ has "happened" (all its elements are present in the context), then every element of that MCS is an actual cause under AC-o and AC-u.
Equivalence: For tree-shaped FTs or FTs in Disjunctive Normal Form (DNF), the condition that an element belongs to a "happened" MCS is both necessary and sufficient for it to be an actual cause under AC-o and AC-u.
AC-m and MCSs: The paper shows that MCSs can be classified in terms of AC-m, specifically relating them to the minimality of sets that prevent failure when removed.

3. Computational Complexity

The paper determines the hardness of computing actual causes in FTs:

AC-o and AC-m: Determining if a specific set is an actual cause is NP-complete.
AC-u: Determining if a specific set is an actual cause is solvable in polynomial time for FTs (unlike the general case which is harder).
Algorithms:
- An algorithm is provided for AC-o that runs in $O(|E|^2|V| + 2^k|E|)$ , where $k$ is the number of "forbidden pairs" (specific gate configurations).
- An algorithm for AC-m reduces the problem to finding Minimal Path Sets (or MCSs of the dual tree), with complexity $O(2^{|BET|}|E|)$ .
- For AC-u, the authors note that existing approaches require enumerating paths, leading to exponential time complexity ( $O(2^{|V|}|V|^2|E|^2)$ ), and leave the development of a more efficient algorithm as future work.

Significance and Claims

The paper claims to offer the first systematic application of the Halpern & Pearl actual causality framework to Fault Trees. Its primary significance lies in:

Unifying Risk and Diagnosis: It enables FTs to move beyond predictive risk assessment ("what can go wrong") to systematic incident analysis ("why did it go wrong").
Graph vs. Logic Distinction: It demonstrates that for AC-o and AC-u, the graph structure of the FT matters, not just the Boolean function. This highlights that intermediate gates represent distinct, intervenable events, a nuance lost in standard FT analysis which treats equivalent structures as identical.
Theoretical Grounding: It provides a rigorous classification of how different causality definitions interact with the specific properties of Fault Trees (coherence, monotonicity, Boolean nature).
Foundation for Future Tools: The work lays the groundwork for integrating causal reasoning (interventions and counterfactuals) into reliability engineering, potentially enhancing failure diagnostics and explanation.

The authors remain modest regarding immediate practical application, noting that while they provide algorithms, a full computational study on real-world scaling is left for future work. They also identify the integration of probabilistic reasoning (via Bayesian Networks) and design-time causality analysis as natural extensions of their current theoretical results.