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

Published

Journal Article

© 1993 ACM. 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.

Full Text

Duke Authors

Cited Authors

  • Cole, R; Maggs, B; Sitaraman, R

Published Date

  • June 1, 1993

Published In

Volume / Issue

  • Part F129585 /

Start / End Page

  • 561 - 572

International Standard Serial Number (ISSN)

  • 0737-8017

Digital Object Identifier (DOI)

  • 10.1145/167088.167235

Citation Source

  • Scopus