CaltechAUTHORS
  A Caltech Library Service

Fault-Tolerant Cube Graphs and Coding Theory

Bruck, Jehoshua and Ho, Ching-Tien (1995) Fault-Tolerant Cube Graphs and Coding Theory. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1995.ETR007

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

1183Kb
[img]
Preview
Postscript
See Usage Policy.

513Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1995.ETR007

Abstract

Hypercubes, meshes, tori and Omega networks are well known interconnection networks for parallel computers. The structure of those graphs can be described in a more general framework called cube graphs. The idea is to assume that every node in a graph with q to the power of l (letter l) nodes is represented by a unique string of l (letter l) symbols over GF(q). The edges are specified by a set of offsets, those are vectors of length l (letter l) over GF(q), where the two endpoints of an edge are an offset apart. We study techniques for tolerating edge faults in cube graphs that are based on adding redundant edges. The redundant graph has the property that the structure of the original graph can be maintained in the presence of edge faults. Our main contribution is a technique for adding the redundant edges that utilizes constructions of error-correcting codes and generalizes existing ad-hoc techniques.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr007.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1995.ETR007
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:1995.ETR007
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:26067
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