Searching with Permanently Faulty Tests

We investigate searching strategies for the set \(\{1, \ldots, n\}\) assuming a fixed bound on the number of erroneous answers and forbidding repetition of questions. This setting models the situation when different processors provide answers to different tests and at most \(k\) processors are faulty. We show for what values of \(k\) the search is feasible and provide optimal testing strategies if at most one unit is faulty.