  This paper considers the problem of approximating the failure frequency of
large-scale composite $k$-terminal reliability systems. In such systems, the
nodes ($k$ of which are terminals) are connected through components which are
subject to random failure and repair processes. At any time, a system failure
occurs if the surviving system fails to connect all the k terminals together.
We assume that each component's up-times and down-times follow statistically
independent stationary random processes, and these processes are statistically
independent across the components. In this setting, the exact computation of
failure frequency is known to be computationally intractable (NP-hard). In this
work, we present an algorithm to approximate the failure frequency for any
given multiplicative error factor that runs in polynomial time in the number of
(minimal) cutsets. Moreover, for the special case of all-terminal reliability
systems, i.e., where all nodes are terminals, we propose an algorithm for
approximating the failure frequency within an arbitrary multiplicative error
that runs in polynomial time in the number of nodes (which can be much smaller
than the number of cutsets). In addition, our simulation results confirm that
the proposed method is much faster and more accurate than the Monte Carlo
simulation technique for approximating the failure frequency.
