Affordable Access

Publisher Website

Determining Performance Measures of Algorithm-Based Fault Tolerant Systems

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
18
Issue
1
Identifiers
DOI: 10.1006/jpdc.1993.1044
Disciplines
  • Computer Science

Abstract

Abstract The analysis problem for a given Algorithm-Based Fault Tolerant (ABFT) system involves determining two important performance measures of the system, namely, its error-detectability and its fault-detectability. Our results clearly delineate the computationally intractable and the efficiently solvable versions of the analysis problem. Specifically, we show that the problems of determining the error-detectability and the fault-detectablity of a given system are, in general, Co-NP-complete and hence unlikely to be efficiently solvable. We also present efficient algorithms for several restricted versions of these problems. In addition, we present a new branch-and-bound algorithm to determine the error-detectability of a system. This algorithm, which runs in O(( g − 1) l ) time where g is the maximum number of data items included in a test (check) and l is the number of tests, is suitable for systems with a small value of l.

There are no comments yet on this publication. Be the first to share your thoughts.