Fault-tolerant search algorithms

THE TOPIC

A large part of research in this area was motivated by the following problem of S. M. Ulam published in his scientific autobiography ``Adventures of a Mathematician'': What is the minimal number of yes-no queries sufficient to find an integer between one and one million, if one lie is allowed among the answers? More generally, one may ask about efficient algorithms for well known combinatorial problems, such as searching, sorting, selection, group testing etc., performed with the use of unreliable tests. Two alternative assumptions about errors in test outcomes are usually made. The number of errors may be either bounded (by a constant or by a function of the number of questions) and their occurrence assumed worst case, or errors may be random and occur independently with given probability. The problem of finding optimal searching strategies with erroneous answers to queries is closely related to the problem of finding shortest error-correcting codes of given size. In fact the former is an adaptive version of the latter.

SELECTED RESULTS

In [P2-87] the original problem of Ulam was solved. The minimum number of questions and the optimal questioning algorithm were given for search with at most one error in an arbitrary finite set. In [CMP-88] and [CMP-89] the case of two errors was solved. In [P3-89] the problem of searching with random errors was investigated. In [P1-89], [P2-94], [CDP-94] and [DDPP-00] other combinatorial problems with unreliable tests were investigated: searching for a heavier coin when weighings may give unreliable results [P1-89], group testing with random errors in test outcomes [P2-94], sorting on a mesh when comparisons between neighbors may fail randomly [CDP-94], and selection in comparator networks with faulty comparators [DDPP-00]. [P-02] is a survey of this domain.

PUBLICATIONS IN THIS DOMAIN

2002 2000 1994 1991 1989 1988 1987 1986