In this research paper, the authors derive new algorithms for reconfiguring interprocessor connections in a rectangular array of processors when some of the processors in the array are faulty. The idea is to reconfigure the connections so that, in effect, spare processors on the borders of the array are incorporated into the array, while preserving the geometry and connectivity of the array. The authors derive an efficient constructive algorithm for determining feasible reconfigurations, if any, for an array with a given distribution of faulty processors for grids with single-track switch models. The time complexity of this algorithm is quadratic in the number of faulty processors. To solve the more general cases of augmented single-track switch models and multiple-track switch models in an n×n grid of processors, the authors convert the problem to one of finding the maximum flow in a network constructed from the grid including the faulty processors. They derive a constructive algorithm for determining the feasibility of reconfiguring the connections, which has time complexity O(n³).

This well-written document has a few inconsistencies in terminology, but they are not serious enough to interfere with the reader’s comprehension of the material. It should interest anyone who works in the area of fault-tolerant networks.