Combinatorial Analysis of the Fault-diameter of the N-cube

Document Type

Article

Publication Date

1-1993

Publication Title

IEEE Transactions on Computers

Volume

42

First page number:

27

Last page number:

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

Computer network resources; Fault-tolerant computing; Hypercube networks (Computer networks); Routing (Computer network management)

Disciplines

Computer and Systems Architecture | Computer Engineering | Digital Circuits | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS