Breaking the Limits of Redundancy Systems Analysis

Clemens Dubslaff, Kai Ding, Andrey Morozov, Christel Baier, Klaus Janschek

Abstract

Redundancy mechanisms such as triple modular redundancy protect safety-critical components by replication and thus improve systems fault tolerance. However, the gained fault tolerance comes along with costs to be invested, e.g., increasing execution time, energy consumption, or packaging size, for which constraints have to be obeyed during system design. This turns the question of finding suitable combinations of components to be protected into a challenging task as the number of possible protection combinations grows exponentially in the number of components. We propose family-based approaches to tackle the combinatorial blowup in redundancy systems modeling and analysis phases. Based on systems designed in SIMULINK we show how to obtain models that include all possible protection combinations and present a tool chain that, given a probabilistic error model, generates discrete Markov chain families. Using symbolic techniques that enable concise family representation and analysis, we show how SIMULINK models of realistic size can be protected and analyzed with a single family-based analysis run while a one-by-one analysis of each protection combination would clearly exceed any realistic time constraints.

Introduction

In safety-critical engineering, such as avionics or medical devices, redundancy is the gold standard for ensuring reliability. Mechanisms like Triple Modular Redundancy (TMR) allow a system to continue functioning even if individual components fail. However, redundancy is not "free"—it introduces overhead in terms of weight, power consumption, and execution time.

Engineers face a complex optimization challenge: which specific components should be made redundant to meet safety requirements without exceeding resource constraints? As the number of components ($N$) increases, the number of possible protection configurations grows exponentially ($2^N$ or more). Analyzing these configurations individually is computationally prohibitive for complex systems. This research introduces a "family-based" approach to break this combinatorial blowup by analyzing the entire set of possible designs in a single pass.

Methodology: The Family-Based Toolchain

The proposed approach integrates system design with formal verification through a specialized toolchain. The process begins with a standard Simulink model where engineers annotate blocks as candidates for protection.

The toolchain workflow from annotated Simulink models to DTMC families.

The toolchain follows these key steps:

  1. Redundancy Pattern Injection: Annotated blocks are automatically replaced with "switchable" redundancy patterns, such as Comparison, Voting, or Sparing.
  2. Family-Based Translation: Using tools like SIMPARS and OPENERRORPRO, the model is converted into a Discrete-time Markov Chain (DTMC) family. This single mathematical model encapsulates every possible configuration.
  3. Symbolic Model Checking: The family is analyzed using PRISM, a probabilistic model checker. By utilizing Multi-Terminal Binary Decision Diagrams (MTBDDs), the analysis can efficiently represent and process systems with many identical components.
  4. State-Space Optimization: Techniques like "Reset Value Optimization" and "Iterative Variable Reordering" are employed to keep symbolic representations compact, enabling the analysis of massive state spaces.

Case Studies and Evaluation

The methodology was evaluated on two primary models:

  • PID Controller: A foundational model with 3 protectable components (64 combinations).
  • Aircraft Velocity Control Loop (VCL): A realistic, large-scale model with 8 protectable components, resulting in 65,536 possible combinations and a state space exceeding $10^{11}$ states.

The core insight is that different protection configurations share significant behavioral similarities. Symbolic analysis "compresses" these similarities, allowing the tool to solve the entire family nearly as quickly as a single instance.

Results and Tradeoff Analysis

The family-based analysis achieved a massive speedup. For the Aircraft VCL model, the all-in-one analysis took approximately 4.8 hours. In contrast, analyzing each of the 65,536 combinations individually was estimated to take 250 days.

Pareto front showing the tradeoff between probability of failure and execution time.

Beyond speed, the analysis generates a Pareto front, visualizing the exact tradeoffs between failure probability and execution time. This allows engineers to identify the "sweet spot" for their specific constraints. The results showed that while "Comparison" and "Voting" patterns offer the highest reliability, they also incur the greatest time costs, whereas "Sparing" is faster but less reliable.

Conclusion and Future Work

While the family-based approach successfully tackles combinatorial blowup, some manual intervention is still required for specific optimizations in large-scale models. Future work aims to fully automate these steps within the OPENERRORPRO tool. Additionally, extending the framework to handle continuous-time models and more complex error distributions remains an open challenge. By leveraging symbolic techniques, this research provides a scalable path for optimizing redundancy in the next generation of safety-critical systems.

Reference: Dubslaff, C., Ding, K., Morozov, A., Baier, C., & Janschek, K. (2019). Breaking the Limits of Redundancy Systems Analysis. Proceedings of the 29th European Safety and Reliability Conference (ESREL).

Summary updated

Abstract

Redundancy mechanisms such as triple modular redundancy protect safety-critical components by replication and thus improve systems fault tolerance. However, the gained fault tolerance comes along with costs to be invested, e.g., increasing execution time, energy consumption, or packaging size, for which constraints have to be obeyed during system design. This turns the question of finding suitable combinations of components to be protected into a challenging task as the number of possible protection combinations grows exponentially in the number of components. We propose family-based approaches to tackle the combinatorial blowup in redundancy systems modeling and analysis phases. Based on systems designed in SIMULINK we show how to obtain models that include all possible protection combinations and present a tool chain that, given a probabilistic error model, generates discrete Markov chain families. Using symbolic techniques that enable concise family representation and analysis, we show how SIMULINK models of realistic size can be protected and analyzed with a single family-based analysis run while a one-by-one analysis of each protection combination would clearly exceed any realistic time constraints.
BibTeX
@inproceedings{dubslaff2019breaking,
  author = {Clemens Dubslaff and Kai Ding and Andrey Morozov and Christel Baier and Klaus Janschek},
  title = {{Breaking the Limits of Redundancy Systems Analysis}},
  booktitle = {Proceedings of the 29th European Safety and Reliability Conference (ESREL)},
  year = {2019},
  doi = {10.3850/978-981-11-2724-3\_0618-cd},
}
Figure