Fault tolerance measures for m-ary n-dimensional hypercubes based on forbidden faulty sets

Abstract

In this paper, we study fault tolerance measures for m-ary n-dimensional hypercubes based on the concept of forbidden faulty sets. In a forbidden faulty set, certain nodes cannot be faulty at the same time and this model can better reflect fault patterns in a real system than the existing ones. Specifically, we study the bounds of the minimum vertex cut set for m-ary n-dimensional hypercubes by requiring each node to have at least k healthy neighbors. Our result enhances and generalizes a result by Latifi et al. for binary hypercubes. Our study also shows that the corresponding result based on the traditional fault model (where k is zero) tends to underestimate network resilience of large networks such as m-ary n-dimensional hypercubes.