NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Efficient diagnosis of multiprocessor systems under probabilistic modelsThe problem of fault diagnosis in multiprocessor systems is considered under a probabilistic fault model. The focus is on minimizing the number of tests that must be conducted in order to correctly diagnose the state of every processor in the system with high probability. A diagnosis algorithm that can correctly diagnose the state of every processor with probability approaching one in a class of systems performing slightly greater than a linear number of tests is presented. A nearly matching lower bound on the number of tests required to achieve correct diagnosis in arbitrary systems is also proven. Lower and upper bounds on the number of tests required for regular systems are also presented. A class of regular systems which includes hypercubes is shown to be correctly diagnosable with high probability. In all cases, the number of tests required under this probabilistic model is shown to be significantly less than under a bounded-size fault set model. Because the number of tests that must be conducted is a measure of the diagnosis overhead, these results represent a dramatic improvement in the performance of system-level diagnosis techniques.
Document ID
19900002896
Document Type
Contractor Report (CR)
Authors
Blough, Douglas M. (California Univ. Irvine., United States)
Sullivan, Gregory F. (Johns Hopkins Univ. Baltimore, MD., United States)
Masson, Gerald M. (Johns Hopkins Univ. Baltimore, MD., United States)
Date Acquired
September 6, 2013
Publication Date
January 1, 1989
Subject Category
COMPUTER SYSTEMS
Report/Patent Number
NASA-CR-185965
NAS 1.26:185965
Funding Number(s)
CONTRACT_GRANT: NSG-1442
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 19900002896.pdf STI