Depth-First Event Ordering in BDD-Based Fault Tree Analysis

Abstract

In BDD-based fault tree analysis, the size of BDD encoding fault trees heavily depends on the chosen ordering. From a theoretical point of view, finding the best ordering is an intractable task. So, heuristics are used to get good orderings. The most simple, and often one of the best heuristics is depth first left most (DFLM) heuristic. Although having been used widely, the performance of DFLM heuristic is still only vaguely understood, and not much formal work has been done. This paper starts from two different research objects: fault tree without repeated events (NRFT) and fault tree with repeated events (RFT). For NRFT, the BDD generated according to DFLM ordering is proved to be the smallest BDD with the size equal to the total number of events. For RFT, a randomized algorithm is firstly proposed to create reliable benchmarks including large number of random fault trees with different specificities. Then, these benchmarks are used to perform two types of experiments to study the performance of DFLM heuristic. For RFT with small number of repeated events, it is found that the sizes of the BDD built over DFLM orderings are only slightly larger than the sizes of the RFT with different specificities. However, with the increase of the number of repeated events, we encounter the size explosion problem, and the change of repeated event distribution patterns will have a significant impact on the sizes of the BDD built over DFLM orderings. We also find that the number of repeated events is the more important measure than some other specificities (shape, logical type of top gate and OR/AND gate distribution) to estimate the level of the difficulty in BDD-based fault tree analysis.