Fault-tolerant search algorithms. Reliable computation with unreliable information (Q625104)

This book provides a comprehensive account of a celebrated fault-tolerant searching game, and its algorithmic developments and applications to adaptive coding and communication theory with feedback. Rényi's description of the game is as follows (see [\textit{A. Rényi}, A diary on information theory. Budapest: Akadémiai Kiadó (1984; Zbl 0539.94001)], page 47): {\parindent=6mm\begin{itemize}\item{} [\dots] I made up the following version, which I called ``Bar-kochba with lies''. Assume that the number of questions which can be asked to figure out the ``something'' being thought of is fixed and the one who answers is allowed to lie a certain number of times. The questioner, of course, doesn't know which answer is true and which is not. Moreover the one answering is not required to lie as many times as is allowed. For example, when only two things can be thought of and only one lie is allowed, then 3 questions are needed. [\dots] If there are four things to choose from and one lie is allowed, then five questions are needed. If two or more lies are allowed, then the calculation of the minimum number of questions is quite complicated. [\dots] It does seem to be a very profound problem. [\dots] \end{itemize}} Ulam's description is as follows (see [\textit{S. M. Ulam}, Adventures of a mathematician. New York: Charles Scribner's Sons (1976; Zbl 0352.01009)], page 281): {\parindent=6mm\begin{itemize}\item{} Someone thinks of a number between one and one million (which is just less than \(2^{20}\)). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half million? then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than \(\log_{2}(1000000)\). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer? \end{itemize}} The Rényi-Ulam game is a generalization of the familiar game of Twenty Questions. Here, the two players, named Carole (alias Pinocchio) and Paul (the Questioner), first agree on fixing a finite space \(S\), say a finite set of \(\{0,1,\dots\}\) for definiteness. Then Carole chooses a secret element \(x \in S\), which Paul must find by asking yes-no questions. Both Rényi and Ulam were interested in a situation where up to \(e\) of Carole's answers may be erroneous/mendacious/inaccurate. From Paul's viewpoint it is immaterial whether wrong answers arise just because Carole is sometimes mendacious or unable to give the correct answer, or else distortion may corrupt up to \(e\) of Carole's correct answers, transforming a ``yes'' into a ``no'', or vice versa. Paul's searching strategies must be \(e\)-fault-tolerant. If all questions are asked at the outset, adaptiveness has no role: then any (optimal) \(n\)-question strategy to guess \(x\) with \(e\) lies is immediately recognized as equivalent to an \(e\)-correcting (optimal) code of length \(n\). \textit{Adaptivity} makes the Ulam-Rényi game an important chapter of Berlekamp's communication theory with noise and feedback, as presented in his paper [\textit{E. R. Berlekamp}, in: Error Correct. Codes, Proc. Symp. Madison 1968, 61--88 (1969; Zbl 0176.49404)] (also see [\textit{R. L. Dobrushin}, Teor. Veroyatn. Primen. 3, 395--412 (1958; Zbl 0094.12402)], reprinted in [\textit{D. Slepian} (ed.), Key papers in the development of information theory. IEEE Press Selected Reprint Series. New York, NY: IEEE (1974; Zbl 0910.94002)]). The first part of the book (Chapters 2--5) is concerned with the pervasive role of adaptivity (= feedback) in the many variants of the Rényi-Ulam game. Paul's guessing ability is typically measured by the number \(n=n_S\) of questions needed in his strategy to infallibly guess \(x\in S \), against Carole's most malicious answering strategies. By a \textit{question} it is meant a subset \(Q\) of \(S\). Ceteris paribus, Paul's strategy is more efficient if he can find \(x\) asking ``simple'' questions, such as ``Is \(x<a?\)'', or, more generally, questions \(Q\) represented by short Boolean formulas. To efficiently guess the unknown number \(x \) Paul must learn from experience: thus for the \(t\)th question he must use what he already knows {}from the previous \(t-1\) answers. Adaptivity has a decisive role even when \(e=0\): as a matter of fact, \(m\) adaptive questions always suffice to find an \(m\)-bit integer \(x\) using questions of the form ``Is \(x < a ?\)'', but \(m\) non-adaptive such questions do not suffice. For the Rényi-Ulam game and its variants the book offers a detailed description of a wealth of adaptive algorithms; many of these algorithms due to the author and his co-authors. These algorithms are aimed at achieving efficient coding: Paul must guess the secret number \(x\) by asking as few as possible (simple) questions, relying as little as possible on Carole's feedback. Trivially, in the game without lies the minimum number of questions is logarithmic in the cardinality \(|S|\) of the search space. As explained in Chapters 2 and 3, this state of affairs remains essentially unchanged if there are lies in the answers. Specifically, perfect \(e\)-correcting codes can be achieved by (minimally) adaptive questions, but cannot if all questions are asked at the outset, already for \(e=2\). Traditional error correcting codes are nonadaptive: all questions are asked at the outset in a unique batch. In Chapter 4 one can find a detailed account to ``two-batch'' (perfect) coding, where a first large batch of questions is asked nonadaptively at the outset and a second final (logarithmic) batch is asked depending on the answers to the first batch. In two-batch perfect coding the costs of feedback are reduced to a minimum. Formalization has an especially interesting role in the Rényi-Ulam game model of fault-tolerant search. Paul's state of knowledge at time \(t\) amounts to the ``conjunction'' \({\mathbb Q}_t\) of Carole's answers to his questions \(Q_1,\dots, Q_{t-1}\). It is known that Paul's deduction of \(x\) from \({\mathbb Q}_t\) obeys the rules of infinite-valued Łukasiewicz logic \(\text{Ł}_\infty\), just as Boolean logic presides over the game of Twenty Questions without lies. As a result of the fault-tolerance and non-idempotence properties of \(\text{Ł}_\infty\), in sharp distinction with Boolean logic, when \(e>0\) relevant information about \(x\) is obtainable from contradictory pieces of information; further, the information contained in two equal answers to the same repeated question exceeds the information given by just one answer. Since a question is just a subset \(Q\) of the search space \(S\), and since (by a theorem of Shannon) almost all Boolean functions describing subsets of \(\{0,\dots,2^n-1\}\) have an exponential length, efficiency requires that the formal complexity of questions/answers should be as small as possible. In Chapters 4 and 5 one can find a detailed account of various types of questions, beyond the paradigm of binary questions asked in the classical Rényi-Ulam game: for instance, the author considers interval and bi-interval questions, \(k\)-ary questions \(K\) (where Carole is asked to locate \(x\) in one among the \(k\) blocks of a partition \(K\) of \(S\)). Various arrangements of the lie structure (beyond the classical cardinality parameter \(e\)) are considered in the final part of Section 5. A notable example is given by assuming ``random lies'' in a Rényi-Ulam game. The book also gives a detailed account of \textit{asymmetric lie patterns}: for instance, in optical transmission, error patterns are highly asymmetric, in that only one of the two bits can be distorted. Optimal error-correcting codes for these asymmetric channels with feedback are the solutions of the ``half-lie'' variant of the Ulam-Rényi problem, asking for the minimum number of yes-no questions needed to find an unknown \(m\)-bit number if up to \(e\) of the \textit{negative} answers may be erroneous/mendacious. Broadening the perspective of Rényi-Ulam games, the second half of the book (pp. 99--198) is concerned with other types of fault-tolerant search algorithms. Chapter 6 deals with the theory of ``erasure-errors'', where errors are no longer understood as false replies, but as lost (or refused) answers. One assumes there is a time-out parameter \(d\), standing for the maximum waiting time for the Receiver (the Questioner) to receive the answer. After the deadline has expired, the undelivered bit is automatically destroyed, so as to prevent desynchronization of the communication channel. The author shows that there is a correspondence between fastest broadcasting protocols over a point-to-point network, and shortest search strategies in a Rényi-Ulam game where only comparison questions are asked. Chapter 7 deals with ``group testing'', where a set \(X\) of elements of a search space \(S\) has to be identified, queries are subsets of \(S\), and a question \(Q\subseteq S\) is answered positively iff it has nonempty intersection with \(X\). Focusing on applications in biology, the author analyzes how errors impinge upon the test structure, with particular reference to ``inhibitory errors'', i.e. members of \(S\) that invalidate a test. Memory faults and resilient search are the subject matter of Chapter 8. Here the author is concerned with the effect of random memory faults on search algorithms. Differently from our remark above concerning the role of non-idempotence in the logic of Rènyi-Ulam games, here two equal answers to the same repeated questions never carry more information than a single answer, because the repeated probe of a corrupted location always outputs the same wrong value. The author computes the maximum number of tolerable memory faults by an algorithm that reports the correct answer, without significantly diverging from the optimal algorithm for the case of no memory faults. The final Chapter 9 deals with the mutual interactions between fault-tolerant search (á la Rényi-Ulam) and a model of computational learning in a noisy environment, in the light of a classical theorem of Rényi. It is shown that prediction with expert advice amounts to a ``gambling'' variant of the Rényi-Ulam game. Optimal solutions for both problems are then obtained. The book is well-written and well-organized, and provides a rigorous and up-to-date account of a wide area of algorithmic fault-tolerant search. Each chapter is supplemented with useful bibliographical notes and exercises. All necessary background material on error-correcting codes is provided in Chapter 3. The other prerequisites are minimal. This book will be useful to students and researchers in many diverse areas, ranging from combinatorial search, to learning and coding theory. It is a most valuable addition to the EATCS Series ``Monographs in Theoretical Computer Science''.