''Dependent & Multimode Failures in Reliability Evaluation of Extra-Stage Shuffle-Exchange MINs''
Jerry L. Trahan
Daniel X. Wang
IEEE Trans. Reliability, vol. 44, no. 1, pp. 73-86, 1995
Previous reliability evaluation efforts for Multistage Interconnection
Networks (MINs) assumed that all failures are statistically
independent and that no degraded operational modes exist for
switches, though these assumptions are inconsistent with
realistic conditions. For example, researchers have described
instances of dependent failures, or fault side-effects, in some MINs.
This paper presents efficient algorithms for terminal, broadcast, and
K-terminal reliability evaluation of the Shuffle-Exchange Network
with an Extra stage (SENE), a redundant path MIN, under assumptions
that allow dependence between failures and degraded operational modes
for switches. A modified shock model incorporates failure dependency
and multiple operational modes into the reliability evaluation.
For an N x N SENE, the reliability algorithms run in
time O(log N), O(log N), and O(k log N), respectively,
where k = | K |.