A Caltech Library Service

Fault-tolerant de Bruijn and shuffle-exchange networks

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. doi:10.1109/71.282566.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
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
Issue or Number:5
Record Number:CaltechAUTHORS:BRUieeetpds94
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6633
Deposited By: Archive Administrator
Deposited On:15 Dec 2006
Last Modified:08 Nov 2021 20:35

Repository Staff Only: item control page