Skip to main content

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

Publication ,  Journal Article
Cole, R; Maggs, B; Sitaraman, R
Published in: Proceedings of the Annual ACM Symposium on Theory of Computing
June 1, 1993

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.

Duke Scholars

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

Publication Date

June 1, 1993

Volume

Part F129585

Start / End Page

561 / 572
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cole, R., Maggs, B., & Sitaraman, R. (1993). Multi-scale self-simulation: A technique reconfiguring arrays with faults. Proceedings of the Annual ACM Symposium on Theory of Computing, Part F129585, 561–572. https://doi.org/10.1145/167088.167235
Cole, R., B. Maggs, and R. Sitaraman. “Multi-scale self-simulation: A technique reconfiguring arrays with faults.” Proceedings of the Annual ACM Symposium on Theory of Computing Part F129585 (June 1, 1993): 561–72. https://doi.org/10.1145/167088.167235.
Cole R, Maggs B, Sitaraman R. Multi-scale self-simulation: A technique reconfiguring arrays with faults. Proceedings of the Annual ACM Symposium on Theory of Computing. 1993 Jun 1;Part F129585:561–72.
Cole, R., et al. “Multi-scale self-simulation: A technique reconfiguring arrays with faults.” Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F129585, June 1993, pp. 561–72. Scopus, doi:10.1145/167088.167235.
Cole R, Maggs B, Sitaraman R. Multi-scale self-simulation: A technique reconfiguring arrays with faults. Proceedings of the Annual ACM Symposium on Theory of Computing. 1993 Jun 1;Part F129585:561–572.

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

Publication Date

June 1, 1993

Volume

Part F129585

Start / End Page

561 / 572