HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 10:13:40 AM
Last modification on : Friday, February 4, 2022 - 3:31:08 AM


  • HAL Id : inria-00100040, version 1



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



Record views