The author presents a new design, called fault-tolerant hypercube (FTH), obtained by augmenting the hypercube topology with some extra links. The FTH has a graceful degradation in performance with the existence of faults. The hardware (link redundancy) is small and negligible for hypercubes with large dimensions. A probabilistic model based on a Markov chain characterizes the FTH-subcube reliability. The mean time to failure is at least 22% better than that for the conventional hypercube. The results have been verified by Monte Carlo simulation. The FTH design is simple and easy to implement. This network can lend itself to the execution of many parallel algorithms designed to run on hypercubes. The FTH contains many more subcubes than the ...