CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetpds94

[img]
Preview
PDF
See Usage Policy.

674Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetpds94

Abstract

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
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
Record Number:CaltechAUTHORS:BRUieeetpds94
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetpds94
Alternative URL:http://dx.doi.org/10.1109/71.282566
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6633
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:15 Dec 2006
Last Modified:26 Dec 2012 09:23

Repository Staff Only: item control page