Fast Computation Using Faulty Hypercubes
Abstract
Consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. Describe a randomized algorithm which embeds an N-node hypercube in an N-node hypercube with faulty processors. Provided that the processors of the N-node hypercube are faulty with probability p<1, and that the faults are independently distributed, we show that with high probability, the faulty hypercube can emulate the fault- free hypercube with only constant slowdown. In other words, an N-node hypercube with faults can simulate T steps of an N-node fault-free hypercube in O(T) steps. The embedding is easy to construct in polylogarithmic time using only local control. Also describe O (log N)-step routing algorithms which ensure the delivery of messages with high probability even when a constant fraction of the nodes and edges have failed. The routing results represent the first adaptive routing algorithms for which an effective theoretical analysis has been achieved.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA211910
Entities
People
- Johan Hastad
- M. E. J. Newman
- Tom Leighton
Organizations
- Massachusetts Institute of Technology