Reconfiguring arrays with faults part I: Worst-case faults

Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman

Research output: Contribution to journalArticle

Abstract

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 N1-∈ 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 logk N worst-case faults, for any constant k > 0, and still emulate a fault-free array with constant slowdown, and this bound is tight.

Original languageEnglish (US)
Pages (from-to)1581-1611
Number of pages31
JournalSIAM Journal on Computing
Volume26
Issue number6
DOIs
StatePublished - Dec 1997

Keywords

  • Array-based network
  • Fault tolerance
  • Mesh network
  • Network emulation

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Reconfiguring arrays with faults part I: Worst-case faults'. Together they form a unique fingerprint.

Cite this