R.J. Cole, B.M. Maggs, and R.K. Sitaraman,

SIAM Journal on Computing, 26(1997), 1581-1611. Preliminary version, Proceedings of the Twenty Fifth Annual ACM Symposium on the Theory of Computing, 1993, 561-570.

This paper studies the ability of array-based networks to tolerate faults. It shows that an N-by-N two-dimensional array can sustain N^(1-epsilon) worst-case faults, for any fixed epsilon > 0, and still emulate a fully-functioning N-by-N array with only constant slowdown. Previously, it was not known if more than a constant number of faults could be tolerated with constant slowdown.

postscript of full paper