Tolerating faults in a mesh with a row of spare nodes

We present an efficient method for tolerating faults in a twodimensional mesh architecture. Our approach is based on adding spare components (nodes) and extra links (edges) such that the resulting architecture can be reconfigured as a mesh in the presence of faults. We optimize the cost of the faulttolerant mesh architecture by adding about one row of redundant nodes in addition to a set of к spare nodes (while tolerating up to к node faults) and minimizing the number of links per node. Our results are surprisingly efficient and seem to be practical for small values of k. The degree of the faulttolerant architecture is к + 5 for odd k, and к + 6 for even k. Our results can be generalized to ddimensional meshes such that the number of spare nodes is less than the length of the shortest axis plus k, and the degree of the faulttolerant mesh is (dl)fc + d + 3 when к is odd and (dl)k + 2d + 2 when к is even.