Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)
Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish S. Rao, Clark D. Thomborson, A. Tsantilas · 1990
In the paper, we analyze the computational power of 2 and 3-dimensional processor arrays that contain a potentially large number of faults. We consider both a random a and worst-case fault model, and we prove that in either scenario, low-dimensional arrays are surprisingly fault-tolerant. For example, we show how to emulate an n e x n m fault-free array on an n x n array containing Q(n2) random faults with sIowdown O(logn), the same slowdown that is used by a fault-free n x n array to perform the simulation. We also show how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, we show that any constant congestion embedding of an n x n fault-free array on an n x n array with @(n2) random faults (or 0(log n) worst-case faults) requires dilation Q(1ogn). For 3-d arrays, we use knot theory to prove that the required dilation is n(*.