The worst-case chip problem

Abstract : In the system level, adaptive fault diagnosis problem we must determine which components (chips) in a system are defective, assuming the majority of them are good. Chips are tested as follows: Take two chips, say x and y, and have x report whether y is good or bad. If x is good, the answer is correct, but if x is bad, the answer is unreliable. One way to identify all defective chips is to identify a single good chip which can then be used to diagnose the other chips; the chip problem is to identify a single good chip. We show that the chip problem is closely related to a modified majority problem in the worst case and use this fact to obtain upper and lower bounds on algorithms for the chip problem.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2004, 89 (6), pp.303-308
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:40
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24


  • HAL Id : inria-00100040, version 1



Laurent Alonso, Philippe Chassaing, Edward M. Reingold, René Schott. The worst-case chip problem. Information Processing Letters, Elsevier, 2004, 89 (6), pp.303-308. 〈inria-00100040〉



Consultations de la notice