Combinatorial analysis of the fault-diameter of the n-cube

Author

Latifi, Shahram

Author_Institution

Dept. of Electr. & Comput. Eng., Nevada Univ., Las Vegas, NV, USA

Volume

42

Issue

1

fYear

1993

fDate

1/1/1993 12:00:00 AM

Firstpage

27

Lastpage

33

Abstract

It is shown that the diameter of an n-dimensional hypercube can only increase by an additive constant of 1 when (n-1) faulty processors are present. Based on the concept of forbidden faulty sets, which guarantees the connectivity of the cube in the presence of up to (2n-3) faulty processors. It is shown that the diameter of the n-cube increases to (n-2) as a result of (2n-3) processor failures. It is also shown that only those nodes whose Hamming distance is (n-2) have the potential to be located at two ends of the diameter of the damaged cube. It is proven that all the n-cubes with (2n-3) faulty processors and a fault-diameter of (n+2) are isomorphic. A generalization to the subject study is presented

Keywords

fault tolerant computing; hypercube networks; Hamming distance; combinatorial analysis; connectivity; fault-diameter; faulty processors; n-dimensional hypercube; Fault tolerance; Hamming distance; Hypercubes; Information science; Multiprocessor interconnection networks; Resilience; Terminology;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.192211

Filename

192211