Distributed fault-tolerant ring embedding and reconfiguration in hypercubes

To embed a ring in a hypercube is to find a Hamiltonian cycle through every node of the hypercube. It is obvious that no 2(n)-node Hamiltonian cycle e xists in an n-dimensional faulty hypercube which has at least one faulty no de. However, if a hypercube has faulty links only and the number of faulty links is at most n - 2, at least one 2(n)-node Hamiltonian cycle can be fou nd. In this paper, we propose a distributed ring-embedding algorithm that c an find a Hamiltonian cycle in a fault-free or faulty n-dimensional hypercu be (Q(n)), and the complexity is O(n) parallel steps. The algorithm is base d on the recursion property of the hypercube and the free-link dimension co ncept. In some cases, even when the number of faulty links is larger than n - 2, Hamiltonian cycles may still exist. We will show that the largest pos sible number of faulty links that can be tolerated is 2(n-1) - 1. The perfo rmance and the constraints of the fault-tolerant algorithm is also analyzed in detail in this paper. Furthermore, a dynamic reconfiguration algorithm for an embedded ring is proposed and discussed. Due to the distributed natu re of the algorithms, they are useful for the simulation of ring-based mult iprocessors on MIMD hypercube multiprocessors.