FAULT-TOLERANT DEBRUIJN AND SHUFFLE-EXCHANGE NETWORKS

This paper addresses the problem of creating a fault-tolerant intercon nection network for a parallel computer. Three topologies, namely, the base-2 de Bruijn graph, the base-m de Bruijn graph, and the shuffle-e xchange, are studied. For each topology an N + k node fault-tolerant g raph is defined. These fault-tolerant graphs have the property that gi ven any set of k node faults, the remaining N nodes contain the desire d topology as a subgraph. All of the constructions given here are the best known in terms of the degree of the fault-tolerant graph. We also investigate the use of buses to reduce the degrees of the fault-toler ant graphs still further.