Four fault-free $B_{n-2}$'s in $B_n$ under the random node fault model

Abstract

Let $n\ge 4$. Each $B_{n-2}$ in $B_n$ has one of the forms $a_1{a}_2{X}^{n-2}$, $a_1{X}^{n-2}{a}_2$ and $X^{n-2}{a}_1{a}_2$. Let $1-p$ be the fault probiability of each node in the $n$-dimensional bubble-sort network $B_n$ under the random node fault model. In this paper, we determine the probability that there are four distinct fault-free $B_{n-2}$'s in $B_n$ by considering all possible combinatorial cases of the four fault-free $B_{n-2}$'s.

arXiv comment63 pages, no figure