Skip to main content

Reconfiguring arrays with faults part I: Worst-case faults

Publication ,  Journal Article
Cole, RJ; Maggs, BM; Sitaraman, RK
Published in: SIAM Journal on Computing
January 1, 1997

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.

Duke Scholars

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 1997

Volume

26

Issue

6

Start / End Page

1581 / 1611

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cole, R. J., Maggs, B. M., & Sitaraman, R. K. (1997). Reconfiguring arrays with faults part I: Worst-case faults. SIAM Journal on Computing, 26(6), 1581–1611. https://doi.org/10.1137/S0097539793255011
Cole, R. J., B. M. Maggs, and R. K. Sitaraman. “Reconfiguring arrays with faults part I: Worst-case faults.” SIAM Journal on Computing 26, no. 6 (January 1, 1997): 1581–1611. https://doi.org/10.1137/S0097539793255011.
Cole RJ, Maggs BM, Sitaraman RK. Reconfiguring arrays with faults part I: Worst-case faults. SIAM Journal on Computing. 1997 Jan 1;26(6):1581–611.
Cole, R. J., et al. “Reconfiguring arrays with faults part I: Worst-case faults.” SIAM Journal on Computing, vol. 26, no. 6, Jan. 1997, pp. 1581–611. Scopus, doi:10.1137/S0097539793255011.
Cole RJ, Maggs BM, Sitaraman RK. Reconfiguring arrays with faults part I: Worst-case faults. SIAM Journal on Computing. 1997 Jan 1;26(6):1581–1611.

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 1997

Volume

26

Issue

6

Start / End Page

1581 / 1611

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics