TY - GEN

T1 - Multi-scale self-simulation

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

AU - Cole, Richard

AU - Maggs, Bruce

AU - Sitaraman, Ramesh

N1 - Funding Information:
1Richard Cole is supported in part by NSF grants CCR-8902221, CCR-8906949 and CCR-9202900. 2Ramesh Sitaraman is supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center - NSF-STC88-09648. This research was conducted while the first author was visiting NEC Research Institute.
Publisher Copyright:
© 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027188173&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027188173&partnerID=8YFLogxK

U2 - 10.1145/167088.167235

DO - 10.1145/167088.167235

M3 - Conference contribution

AN - SCOPUS:0027188173

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 561

EP - 572

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

Y2 - 16 May 1993 through 18 May 1993

ER -