CaltechAUTHORS
  A Caltech Library Service

Fault-Tolerant Meshes with Small Degree

Bruck, Jehoshua and Cypher, Robert and Ho, Ching-Tien (1994) Fault-Tolerant Meshes with Small Degree. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1994.ETR001

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

2681Kb
[img]
Preview
Postscript
See Usage Policy.

301Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1994.ETR001

Abstract

This paper presents constructions for fault-tolerant two-dimensional mesh architectures. The constructions are designed to tolerate k faults while maintaining a healthy n by n mesh as a subgraph. They utilize several novel techniques for obtaining trade-offs between the number of spare nodes and the degree of the fault-tolerant network. We consider both worst-case and random fault distributions. In terms of worst-case faults, we give a construction that has constant degree and O(k to the power of 3) spare nodes. This is the first construction known in which the degree is constant and the number of spare nodes is independent of n. In terms of random faults, we present several new degree-6 and degree-8 constructions and show (both analytically and through simulations) that they can tolerate large numbers of randomly placed faults.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr001.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1994.ETR001
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:1994.ETR001
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:26073
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Sep 2002
Last Modified:26 Dec 2012 13:53

Repository Staff Only: item control page