Bruck, Jehoshua and Cypher, Robert and Ho, Ching-Tien (1994) Fault-tolerant de Bruijn and shuffle-exchange networks. IEEE Transactions on Parallel and Distributed Systems, 5 (5). pp. 548-553. ISSN 1045-9219. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetpds94
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetpds94
This paper addresses the problem of creating a fault-tolerant interconnection network for a parallel computer. Three topologies, namely, the base-2 de Bruijn graph, the base-m de Bruijn graph, and the shuffle-exchange, are studied. For each topology an N+k node fault-tolerant graph is defined. These fault-tolerant graphs have the property that given any set of k node faults, the remaining N nodes contain the desired topology as a subgraph. All of the constructions given 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-tolerant graphs still further.
|Additional Information:||© Copyright 1994 IEEE. Reprinted with permission. Manuscript received January 15, 1992; revised May 28, 1993.|
|Subject Keywords:||de Bruijn networks, fault tolerance, reconfiguration, shuffle-exchange networks, spare nodes|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||15 Dec 2006|
|Last Modified:||26 Dec 2012 09:23|
Repository Staff Only: item control page