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)

PDF (Adobe PDF (2.7MB))
See Usage Policy.

See Usage Policy.


Use this Persistent URL to link to this item:


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
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1994.ETR001
Persistent URL:
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
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Sep 2002
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page