Randomness and Robustness in Hypercube Computation
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
In this thesis we explore means by which hypercubes can compute despite faulty processors and links. We also study techniques which enable hypercubes to simulate dynamically changing networks and data structures. In chapter two, we investigate strategies for routing permutations on faulty hypercubes. We assume that each node or edge in the hypercube fails with constant probability and that failures are independent of one another. We describe a routing algorithm which successfully routes messages between working processors in Olog N steps on an N-node faulty hypercube with high probability.
- Computer Hardware