Multi-scale self-simulation: A technique reconfiguring arrays with faults

In this paper we study the ability of array-based networks to tolerate faults. We show that an N x N two- dimensional array can sustain N1-ϵ worst-case faults, for any fixed e > 0, and still emulate a fully functioning N x N array with only constant slowdown. We also observe that even if every node fails with some fixed probability, p, with high probability the array can still emulate a fully functioning array with constant slowdown. Previously, no connected bounded-degree network was known to be able to tolerate constant- probability node failures without suffering more than a constant-factor loss in performance. Finally, we observe that if faulty nodes are allowed to communicate, but not compute, then an N-node one-dimensional array can tolerate log°W N worst-case faults and still emulate a fault-free array with constant slowdown, and this bound is tight.