Probabilistic Reliability via Subsystem Structures of Arrangement Graph Networks

With the rapid growth of the number of processors in a multiprocessor system, faulty processors occur in it with a probability that rises quickly. The probability of a subsystem with an appropriate size being fault-free in a definite time interval is a significant and practical measure of the reliability for a multiprocessor system, which characterizes the functionality of a multiprocessor system well. Motivated by the study of subgraph reliability, as well as the attractive structure and fault tolerance properties of (n, k)-arrangement graph A n, k, we focus on the subgraph reliability for A n, k under the probabilistic fault model in this article. First, we investigate intersections of no more than four subgraphs in A n, k, and classify all the intersecting modes. Second, we focus on the probability P(q, A n, k n-1, k-1) with which at least one (n-1, k-1)-subarrangement graph is fault-free in A n, k, when given a uniform probability q with which a single vertex is fault-free, and we establish the P(q, A n, kn-1, k-1) by adopting the principle of inclusion-exclusion under the probabilistic fault model. Finally, we study the probabilistic fault model involving a nonuniform probability with which a single vertex is fault-free, and we prove that the P(q, A n, kn-1, k-1) under both models is very close to the asymptotic value by both theoretical arguments and experimental results.