Fast computation using faulty hypercubes

ABSTRACT

We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. We 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. We 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.

REFERENCES

• A: F. Annexstein, Fault tolerance in hypercube-derivative networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.179-188, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72955]
• BS: B. Becker and H.U. Simon, "How Robust is the n-Cube?," Proc. 27th Ann. IEEE Syrup. Foundations Comput. $ci., Oct. 1986, pp. 283- 291.
• DHSS: Danny Dolev , Joe Halpern , Barbara Simons , Ray Strong, A new look at fault tolerant network routing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.526-535, December 1984 [doi>10.1145/800057.808723]
• G: E. Giladi, private communication.
• GHLS: N. Graham, F. Harary, M. Livingston, Q. Stout "Subcube Fault-Tolerance in Hypercubes," unpublished manuscript.
• HLN: J. Hastad , T. Leighton , M. Newman, Reconfiguring a hypercube in the presence of faults, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.274-284, January 1987, New York, New York, United States [doi>10.1145/28395.28425]
• R: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• S: J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987.
• VB: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Reliability, Theory, Verification