Computation of k-out-of-n System Reliability via Reduced Ordered Binary Decision Diagrams

A prominent reliability model is that of the partially-redundant (k-out-of-n) system. We use algebraic as well as signal-flow-graph methods to explore and expose the AR algorithm for computing k-out-of-n reliability. We demonstrate that the AR algorithm is, in fact, both a recursive and an iterative implementation of the strategy of Reduced Ordered Binary Decision Diagrams (ROBDDs). The underlying ROBDD for the AR recursive algorithm is represented by a compact Signal Flow Graph (SFG) that is used to deduce AR iterative algorithms of quadratic temporal complexity and linear spatial complexity. Extensions of the AR algorithm for (single or scalar) threshold, double-threshold, vector-threshold, and k-to-l-out-of-n systems have similar ROBDD interpretations.