Depth-First Search Approach for Fault-Tolerant

Abstract-Using depth-first search, we develop and analyze the per-formance of a routing scheme for hypercube multicomputers in the pres-ence of an arbitrary number of faulty components. We derive an exact expression for the probability of routing messages via optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. Also, bounds for this prob-ability are derived in closed form. Note that the probability of routing messages via an optimal path between any two nodes is a special case of our results, and can be obtained by replacing the Obstructed node with the destination node. Numerical examples are also given to illustrate our results, and show that in the presence of component failures the depth-first search routing can route a message via an optimal path to its destination with a very high probability