BOUNDS ON ALGORITHM-BASED FAULT TOLERANCE IN MULTIPLE PROCESSOR SYSTEMS.

被引：38

作者：

Banerjee, Prithviraj ^{[1
]}

Abraham, Jacob A. ^{[1
]}

机构：

[1] Univ of Illinois, Urbana, IL, USA, Univ of Illinois, Urbana, IL, USA

来源：

IEEE Transactions on Computers | 1986年 / C-35卷 / 04期

关键词：

COMPUTER PROGRAMMING - Algorithms - MATHEMATICAL PROGRAMMING; LINEAR - MATHEMATICAL TECHNIQUES - Graph Theory;

D O I：

10.1109/TC.1986.1676762

中图分类号：

学科分类号：

摘要：

The authors present a graph-theoretic model for determining upper and lower bounds on the number of checks needed for achieving concurrent fault detection and location. The objective is to estimate the overhead in time and the number of processors required for such a scheme. Faults in processors, errors in the data, and checks on the data to detect and locate errors are represented as a tripartite graph. Bounds on the time and processor overhead are obtained by considering a series of subproblems. First, using some crude concepts for t-fault detection and t-fault location, bounds on the maximum size of the error patterns that can arise from such fault patterns are obtained. Using these results, bounds are derived on the number of checks required for error detection and location. Some numerical results are derived from a linear programming formulation.

引用

页码：296 / 306