CaltechAUTHORS
  A Caltech Library Service

Optimal Constructions of Fault-Tolerant Multistage Interconnection Networks

Fan, Charles C. and Bruck, Jehoshua (1996) Optimal Constructions of Fault-Tolerant Multistage Interconnection Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1996.ETR014

[img]
Preview
PDF (Adobe PDF (1.3MB))
See Usage Policy.

1274Kb
[img]
Preview
Postscript
See Usage Policy.

310Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1996.ETR014

Abstract

In this paper we discover the family of Fault-Tolerant Multistage Interconnection Networks (MINs) that tolerates switch faults with a minimal number of redundant switching stages. While previously known constructions handled switch faults by eliminating complete stages, our approach is to bypass faulty switches by utilizing redundant paths. As a result, we are able to construct the first known fault-tolerant MINs that are optimal in the number of redundant stages. Our fault model assumes that a faulty switch can be bypassed and our goal is to guarantee arbitrary point to point and broadcast connectivity. Under this model, we show that to tolerate f switch faults the MIN must have at least f redundant stages. We then present the explicit construction of a MIN that meets this lower-bound. This construction repeatedly uses the singleton basis of the n-dimensional vector space as the mask vectors of the MIN. We generalize this construction and prove that an n-dimensional MIN is optimally fault-tolerant if and only if the mask vectors of every n consecutive stages span the n-dimensional vector space.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr014.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1996.ETR014
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:1996.ETR014
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26060
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Sep 2002
Last Modified:26 Dec 2012 13:52

Repository Staff Only: item control page