Searching with Permanently Faulty Tests

Abstract

We investigate searching strategies for the set $\{1,\dots ,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.