OPTIMAL SIMULATION OF FULL BINARY-TREES ON FAULTY HYPERCUBES

We study the problem of running full binary tree based algorithms on a hypercube with faulty nodes. The key to this problem is to devise a m ethod for embedding a full binary tree into the faulty hypercube. Base d on a novel embedding strategy, we present two results for embedding an (n - 1)-tree (a full binary tree with 2(n-1) -1 nodes) into an n-cu be (a hypercube with 2(n) nodes) with unit dilation and load. For the problem where the root of the tree must be mapped to a specified hyper cube node (specified root embedding problem), we show that up to n - 2 (node or edge) faults can be tolerated. This result is optimal in the following sense: 1) it is time-optimal, 2) (n - 1)-tree is the larges t full binary tree that can be embedded in an n-cube, and 3) n - 2 fau lts is the maximum number of worst-case faults that can be tolerated i n the specified root problem. Furthermore, we also show that any algor ithm for this problem cannot be totally recursive in nature, For the p roblem where the root can be mapped to any nonfaulty hypercube node (v ariable root embedding problem), we show that up to 2n - 3 - [log n] f aults can be tolerated. Thus we have improved upon the previous result of n - 1 - [log n]. In addition, we show that the algorithm for the v ariable root embedding problem is optimal, within a class of algorithm s called recursive embedding algorithms as far as the number of tolera ble faults is concerned. Finally, we show that when an 0(1/root n) fra ction of nodes in the hypercube are faulty, it is not always possible to have an O(1)-load variable root embedding no matter how large the d ilation is.