PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Albini L. C., Chessa S., Maestrini P. Diagnosis of Symmetric graphs Under the BGM Model. In: Computer Journal, vol. 47 (1) pp. 85 - 92. Elsevier, 2004.
 
 
Abstract
(English)
This paper addresses the problem of the identification of faulty units in symmetric systems under the diagnostic model proposed by Barsi, Grandoni and Maestrini (hence called the BGM model). The paper introduces and evaluates an algorithm named DABS (Diagnosis Algorithm for Symmetric System under the BGM model). It is shown that DABS provides a diagnosis unconditionally correct although possibly incomplete. A measure of diagnosis incompleteness IDeg(t) has been defined as the quotient between the number of suspect units (that is, the units that DABS is unable to identify as either good or faulty) and the number of system units. IDeg(t) is evaluated over the set of syndromes deriving from at most t faults under the BGM model. A general approach to the evaluation of IDeg(t) in symmetric systems is introduced, and tight bounds to IDeg(t) are derived for square toroidal grids and hypercubes. This bound is O(t/n) in the case of square toroidal grids of n units.
DOI: 10.1093/comjnl/47.1.85
Subject Massively parallel systems
system-level diagnosis
sequencial
C.1.4 Parallel Architectures
D.4.5 OPERATING SYSTEMS. Reliability


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional