The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing

This paper presents the new Flexible Hypercube architecture. The Flexible Hypercube is a fault-tolerant network topology that can be constructed for an arbitrary number of nodes and is incrementally expandable. This topology maintains the strong features of the Hypercube while overcoming deficiencies in expandability. It is shown to have strong node connectivity, a small diameter, and to be tolerant of faults. The Flexible Hypercube is a suitable architecture for the design of both tightly coupled parallel systems and distributed systems. Efficient fault-free and fault-tolerant algorithms for message routing and broadcasting are presented for the architecture. The fault-free algorithm guarantees successful routing inO(logN) time, whereNis the number of nodes in the system, and the fault-tolerant algorithm guarantees routing to functioning nodes if a route exists. The fault-free and fault-tolerant broadcasting algorithms have time complexityO(logN), and the fault-tolerant algorithm guarantees success if no two faulty nodes are adjacent and no functioning node is adjacent to two faults.