Embedding complete binary trees in faulty hypercubes

This paper studies the ability of the hypercube to implement tree-structured algorithms in the presence of faults. The hypercube is able to implement a wide range of algorithms efficiently, and the authors' selection of tree computations is motivated by the fact that many parallel algorithms, including broadcasting, parallel prefix, and other divide-and-conquer algorithms, have a natural tree structure. The authors' primary result is that there exists a function f(n) such that f(n)= Omega (n2/log n) and any n-dimensional hypercube with f(n) faulty nodes and/or edges contains as a subgraph a fault-free complete binary tree with 2/sup n-1/-1 nodes. Previously, the hypercube was known to contain such a tree only when there were fewer than 2n faults. In addition, they prove an upper bound on the number of faults that can be avoided when a natural class of embedding techniques is used.