ON THE CONSTRUCTION OF FAULT-TOLERANT CUBE-CONNECTED CYCLES NETWORKS

This paper presents a new approach to tolerating edge faults and node faults in (CCC) networks of Cube-Connected Cycles in a worst-case scen ario. Our constructions of fault-tolerant CCC networks are obtained by adding extra edges to the CCC. The main objective is to reduce the co st of the fault-tolerant network by minimizing the degree of the netwo rk. Specifically, we have two main results. (i) We have created a faul t tolerant CCC that can tolerate any single fault, either a node fault or an edge fault. When the dimension of the CCC is odd, the degree of the fault tolerant graph is 4. In the even case, there is a single no de per cycle that is of degree 5 and the rest are of degree 4. (ii) We have created a fault-tolerant CCC, where every node has degree y + 2, which can tolerate any 2y - 1 cube-edge faults. Our constructions are extremely efficient for the case of edge faults-they result in health y CCC networks that utilize all of the processors. (C) 1995 Academic P ress, Inc.