# The Chip Problem

1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The chip problem'' is a fault diagnosis problem in which 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 and can be either wrong with probability $\alpha$ or right with probability $1-\alpha$. We show that the chip problem is closely related to a modified majority problem in the {\em worst case} and use this fact to obtain upper and lower bounds on algorithms for the chip problem. We show the limits of this relationship by showing that algorithms for the chip problem can violate lower bounds on {\em average performance} for the modified majority problem and we give an algorithm for the biased chip'' problem (in which $p$ is the probability that a chip is bad) whose average performance is better than the average cost of the best algorithm for the biased majority problem.
Keywords :
Type de document :
Rapport
[Intern report] 98-R-372 || alonso98a, 1998, 28 p
Domaine :

https://hal.inria.fr/inria-00098739
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:22:14
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:46:12

### Identifiants

• HAL Id : inria-00098739, version 1

### Citation

Laurent Alonso, Philippe Chassaing, Edward M. Reingold, René Schott. The Chip Problem. [Intern report] 98-R-372 || alonso98a, 1998, 28 p. 〈inria-00098739〉

### Métriques

Consultations de la notice

## 359

Téléchargements de fichiers