Ring embedding in hypercubes with faculty nodes

Abstract

Hypercube is an attractive structure for parallel processing due to its symmetry and regularity. To increase the reliability of hypercube based systems and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in hypercubes are necessary. In this paper, we present an algorithm for embedding rings in hypercubes based multiprocessor network in the event of node failures. The algorithm can tolerate up to θ(2) faults, and guarantee that given any f < (n -2k)2 faulty nodes, it can find a ring of size at least 2 - 2/ for k = 0 and 2 - 2 f - 2 for k ≥ 1 in an n-dimensional hypercube. It improves over existing algorithms in the size of ring. © World Scientific Publishing Company.