Fault tolerance in hypercube-derivative networks (preliminary version)
- 1 March 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 19 (1) , 25-34
- https://doi.org/10.1145/121956.121959
Abstract
We present algorithms which reconfigure faulty deBruijn and Butterfly networks. We show that, with high probability, an N-node deBruijn (resp., Butterfly) network with uniformly distributed faulty processors can simulate a fault-free N-node deBruijn (resp., Butterfly) network with a slowdown factor of O(log log N). Our configuration algorithm is deterministic, operates in a distributed fashion, uses only local control, and takes time O(log2 N).Keywords
This publication has 6 references indexed in Scilit:
- Efficient dispersal of information for security, load balancing, and fault toleranceJournal of the ACM, 1989
- Fast computation using faulty hypercubesPublished by Association for Computing Machinery (ACM) ,1989
- Broadcasting with random faultsDiscrete Applied Mathematics, 1988
- Universal schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1981
- Optimal Rearrangeable Multistage Connecting NetworksBell System Technical Journal, 1964
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952