CaltechAUTHORS
  A Caltech Library Service

Fault-tolerant cube graphs and coding theory

Bruck, Jehoshua and Ho, Ching-Tien (1996) Fault-tolerant cube graphs and coding theory. IEEE Transactions on Information Theory, 42 (6, pt.). pp. 2217-2221. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetit96

[img]
Preview
PDF
See Usage Policy.

611Kb

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

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 ql nodes is represented by a unique string of l symbols over GF(q). The edges are specified by a set of offsets, those are vectors of length 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:Article
Additional Information:© Copyright 1996 IEEE. Reprinted with permission. Manuscript received September 3, 1995; revised February 16, 1996. This work was supported in part by the NSF Young Investigator Award CCR-9457811, by the Sloan Research Fellowship and under a Grant from the IBM Almaden Research Center, San Jose, CA. The authors wish to thank the Editor and the referees for their comments and suggestions that helped to improve the correspondence.
Subject Keywords:Fault tolerance, parallel computing, interconnection networks, hypercubes, omega networks, error-correcting codes
Record Number:CaltechAUTHORS:BRUieeetit96
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetit96
Alternative URL:http://dx.doi.org/10.1109/18.556609
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5704
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:29 Oct 2006
Last Modified:26 Dec 2012 09:14

Repository Staff Only: item control page