Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 10:13:40 AM
Last modification on : Friday, February 26, 2021 - 3:28:03 PM


  • 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⟩



Record views