Article Sidebar

Submitted
Apr 25, 2017
Published
Jun 1, 2005
Download
PDF
Statistic
Read Counter : 371 Download : 242

Main Article Content

Abstract

We obtain the conditional fault diameter of the k-ary n-cube interconnection network. It has been previously shown that under the condition of forbidden faulty sets (i.e. assuming each non-faulty node has at least one non-faulty neighbor), the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected. We extend this result by showing that the conditional fault-diameter of the k-ary n-cube is equal to the fault-free diameter plus two. This means that if there are at most 4n-3 faulty nodes in the k-ary n-cube and if every non-faulty node has at least one non-faulty neighbor, then there exists a fault-free path of length at most the diameter plus two between any two non faulty nodes. We also show how to construct these fault-free paths. With this result the k-ary n-cube joins a group of interconnection networks (including the hypercube and the star-graph) whose conditional fault diameter has been shown to be only two units over the fault-free diameter.

Keywords

Fault-tolerance multiprocessor systems interconnection architectures k-ary n-cube torus.

Article Details

References

  1. BOSE, B., BROEG, B., KWON, Y. and ASHIR, Y. 1995. Lee distance and topological properties of k-ary n-cubes, IEEE Trans. Computer, 44(8): 1021-1030.
  2. DAY, K. 2004. The Conditional Node-Connectivity of the k-ary n-Cube, Journal of Interconnection Networks, 5(1):13-25.
  3. DAY, K. and Al-AYYOUB, A.E. 1997. Fault Diameter of k-ary n-cube Networks, IEEE Trans. on Parallel and Distributed Systems, 8(9): 903-907.
  4. ESFAHANIAN, A.H. 1989. Generalized Measures of Fault Tolerance with Application to n-Cube Networks, IEEE Trans. on Computers, 38(11): 1586-1591.
  5. LATIFI, S. Combinatorial Analysis of Fault-Diameter of the n-Cube, IEEE Trans. on Computers, 42(1): 27-33,1993.
  6. LATIFI, S., HEGDE, M. and NARAGHI-Pour, M. 1994. Conditional Connectivity Measures for large Multiprocessor Systems, IEEE Trans. on Computers, 43(2): 218-222.
  7. ROUSKOV, Y., LATIFI, S. and SRIMANI, P.K. 1996. Conditional Fault Diameter of Star Graph Networks, Journal of Parallel and Dist. Computing, 33: 91-97.
  8. TOUZENE, A. and DAY, K. 2005. Conditional Fault-Diameter of the Torus, to appear in SQU Journal for Science 10:53-63.
  9. WU, J. 1998. FAULT Tolerance Measures for m-Ary n-Dimensional Hypercube Based on Forbidden Faulty Sets, IEEE Trans. on Comp., 47(8): 888-893.