Optimal simulation of full binary trees on faulty hypercubes

Abstract

The problem of operating full binary tree based algorithms on a hypercube with faulty nodes was investigated. Developing a method for embedding a full binary tree into the faulty hypercube is the solution to this problem. Two outcomes for embedding an (n-1)-tree into an n-cube with unit dilation and load, that were based on a new embedding technique, were presented. For the problem where the root can be mapped to any nonfaulty hypercube node, the optimum toleration of faults was shown. Moreover, it was demonstrated that the algorithm for the variable root embedding problem is maximal within a class algorithms called recursive embedding algorithms as far as the number of tolerable faults is concerned. Lastly, it was demonstrated that when an O(1/√n) fraction of nodes in the hypercube are faulty, a O(1)-load variable root embedding is not always possible regardless of the significance of the dilation.