Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 1, 1994 | public
Report Open

Fault-Tolerant Meshes with Small Degree

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.

Files

etr001.pdf
Files (3.1 MB)
Name Size Download all
md5:98cf39a6efe12f4cf0c3db8ee22801dd
2.7 MB Preview Download
md5:d9f75f46a60a80ea1d40b002246286e4
308.3 kB Download

Additional details

Created:
August 20, 2023
Modified:
October 24, 2023