TOLERATING FAULTS IN A MESH WITH A ROW OF SPARE NODES

We present an efficient method for tolerating faults in a two-dimensio nal mesh architecture. Our approach is based on adding spare component s (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 fault-tolerant mesh architecture by adding about one r ow of redundant nodes in addition to a set of k spare nodes (while tol erating up to k node faults) and minimizing the number of links per no de. Our results are surprisingly efficient and seem to be practical fo r small values of k. The degree of the fault-tolerant architecture is k+5 for odd k, and k+6 for even k. Our results can be generalized to d -dimensional meshes.