A Multiple-Valued Decision-Diagram-Based Approach to Solve Dynamic Fault Trees

摘要

Dynamic fault trees (DFTs) have been used for many years because they can easily provide a concise representation of the dynamic failure behaviors of general non-repairable fault tolerant systems. However, when repeated failure events appear in real-life DFT models, the traditional modularization-based DFT analysis process can still generate large dynamic subtrees, the modeling of which can lead to a state explosion problem. Examples of these kinds of large dynamic subtrees abound in models of real-world dynamic software and embedded computing systems integrating with various multi-function components. This paper proposes an efficient, multiple-valued decision-diagram (MDD)-based DFT analysis approach for computing the reliability of large dynamic subtrees. Unlike the traditional modularization methods where the whole dynamic subtree must be solved using state-space methods, the proposed approach restricts the state-space method only to components associated with dynamic failure behaviors within the dynamic subtree. By using multiple-valued variables to encode the dynamic gates, a single compact MDD can be generated to model the failure behavior of the overall system. The combination of MDD and state-space methods applied at the component or gate level helps relieve the state explosion problem of the traditional modularization method, for the problems we explore. Applications and advantages of the proposed approach are illustrated through detailed analyses of an example DFT, and through two case studies.