The worst-case chip problem |
| |
Authors: | Laurent Alonso René Schott |
| |
Affiliation: | a INRIA-Lorraine and LORIA, Université Henri Poincaré-Nancy I, BP 239, 54506 Vandoeuvre-lès-Nancy, France b Institut Élie Cartan, Université Henri Poincaré-Nancy I, BP 239, 54506 Vandœuvre-lès-Nancy, France c Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue, Urbana, IL 61801, USA d Institut Élie Cartan and LORIA, Université Henri Poincaré-Nancy I, BP 239, 54506 Vandœuvre-lès-Nancy, France |
| |
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. |
| |
Keywords: | Fault diagnosis Analysis of algorithms Chip problem Majority problem |
本文献已被 ScienceDirect 等数据库收录! |
|