| Reconfiguring Arrays with Faults Part I: Worst-Case Faults (1997) | |||||||||||||||
Abstract | |||||||||||||||
| In this paper we study the ability of array-based networks to tolerate worstcase faults. We show that an N \Theta N two-dimensional array can sustain N 1\Gammaffl worst-case faults, for any fixed ffl ? 0, and still emulate a fully functioning N \Theta N array with only constant slowdown. Previously it was known only that an array could tolerate a constant number of faults with constant slowdown. We also show that if faulty nodes are allowed to communicate, but not compute, then an N-node one-dimensional array can tolerate log O(1) N worst-case faults and still emulate a fault-free array with constant slowdown, and this bound is tight. 1 Richard Cole is supported in part by NSF Grants No. CCR-92-02900 and CCR-95-03309. 2 Bruce Maggs is supported in part by an NSF National Young Investigator Award, No. CCR-94-57766, with matching funds provided by NEC Research Institute, and by ARPA Contract F33615-93-1-1330. 3 Ramesh Sitaraman is supported in part by NSF Grant No. CCR-94-1007... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||