Reconfiguring arrays with faults part I: Worst-case faults

Published

Journal Article

In this paper we study the ability of array-based networks to tolerate worst-case faults. We show that an N × N two-dimensional array can sustain N 1-∈ worst-case faults for any fixed ∈ > 0, and still emulate T steps of a fully functioning N × N array in O(T + N) steps, i.e., 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 k N worst-case faults, for any constant k > 0, and still emulate a fault-free array with constant slowdown, and this bound is tight.

Full Text

Duke Authors

Cited Authors

  • Cole, RJ; Maggs, BM; Sitaraman, RK

Published Date

  • January 1, 1997

Published In

Volume / Issue

  • 26 / 6

Start / End Page

  • 1581 - 1611

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/S0097539793255011

Citation Source

  • Scopus