inria-00100040, version 1
The worst-case chip problem
Information Processing Letters 89, 6 (2004) 303-308
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.
- a – INRIA
- b – DCS, UNIVERSITY OF ILLINOIS AT URBANA CHAMPAIGN
- 1:
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- 2:
- CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- 3:
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Domain : Computer Science/Other
- Keywords : fault diagnosis – analysis of algorithms – chip problem – majority problem || analyse d'algorithme – majorité – diagnostique
- Internal note : A04-R-306 || alonso04a
- Comment : Article dans revue scientifique avec comité de lecture. internationale.
- inria-00100040, version 1
- http://hal.inria.fr/inria-00100040
- oai:hal.inria.fr:inria-00100040
- From:
- Submitted on: Tuesday, 26 September 2006 10:13:40
- Updated on: Monday, 11 June 2007 15:26:07
Export