Wildcard Dimensions, Coding Theory and Fault Tolerant Meshes and Hypercubes

Wildcard Dimensions, Coding Theory and Fault Tolerant Meshes and Hypercubes

      Disclosed is an efficient method for tolerating link faults in
a d-dimensional mesh, based on the technique of the so-called
wildcard dimensions and error correcting codes theory.

      It is known that a hypercube can be extended by one wildcard
dimension resulting in a folded hypercube, which has better fault
tolerance and communication capabilities.  Also, a d-dimensional
torus having n nodes can be extended by up to n-d+1 wildcard
dimensions.  Using techniques from error correcting codes,
specifically a Maximum Distance Separable (MDS) code such as the
extended Reed-Solomon codes and an extension of the Vandermonde
matrix, we construct a d-dimensional fault-tolerant mesh which has
degree 2s and can tolerate 2s - 2d+1 edge faults, for any d < s
< n+1, regardless of the faults distribution.  The faults are
tolerated in the sense that the remaining (fault-free) network still
guaranteed to contain a d-dimensional mesh of the same size as a
subgraph.  Thus, programs designed for the original mesh can be run
on the fault-tolerant mesh without slowdown, even after up to 2s -
2d+1 link failures.

      Disclosed anonymously.