The problem considered by this book is how two agents can successfully communicate in the absence of a prior agreement on the protocol to be used. Specific examples of potential applications include interfacing with device drivers and adapting to changing network protocols.
The model that is used involves two agents, Alice and Bob, who engage in a series of “rounds.” Alice sends a message to Bob, who can reply to Alice. Bob has some goal that he would like to achieve, so Alice plays the role that subsequently is called the server and Bob takes on the role of the user. The author considers two kinds of goals that Bob might have. The first is a “one shot goal,”--for example, causing a printer to produce specific text--and the other is to bring about and maintain a specific state. The second kind of goal involves infinite executions, while the first requires only a finite number of executions.
An important component of the model is the requirement for a sensing function, because perhaps the target printer is in another room and thus not visible to the user, for example. There are two important properties for a sensing function: safety and viability. Safety means that if the value of the sensing function is 1, then success has been achieved (however, it is possible for the function to be 0 when success occurs). Viability means that when success has been achieved, the sensing function value is 1. Note that the function that is always 0 is safe and the function that is always 1 is viable, so one wants both. What makes the process more interesting is the presence of an environment that mediates the communication, which itself has a nondeterministic strategy, so that it reports to Alice and Bob in ways that do not necessarily accurately reflect the state of the communication.
Rather than using Alice and Bob throughout, the author casts most of the discussion in terms of a user strategy U (Bob) and a server S (Alice). The user seeks to achieve a goal G with the server S. “A finite goal of communication is given by a pair, consisting of the environment’s nondeterministic probabilistic strategy and a finite referee,” which is a Boolean function on the environment that determines success. A user strategy U robustly achieves a goal with probability p if for every initial state of the user, the probability that the strategy U achieves the goal is p. “A server strategy is p-helpful for a goal G if there exists a polynomial time user protocol U such that (U,S) robustly achieves the goal with probability p.”
The author provides significant examples of conditions to consider, such as a server that is password protected, meaning the server will not respond until the user sends the correct password. In this case, finding a password of length k is exponential in k, unless some shortcut is available, such as a password that appears in the dictionary. In general, finding a robust strategy is a matter of trying alternatives until success is achieved. In this sense, the robust strategies that the author describes rely on enumeration methods similar to those used by Levin in his universal search problems [1] and the anytime algorithms of Russell and Subramanian [2]. The author also makes extensive use of ideas drawn from the theory of interactive proofs.
The main results on one shot goals determine the conditions under which there are robust protocols for achieving the user’s goals. This result is similar to those in the theory of probably approximately correct (PAC) learning algorithms, which is not so surprising when one realizes that the user is trying to learn how to use the server.
To handle the case of infinite executions, it is not possible to use the kind of exhaustive methods from the finite case. Rather, one must rely on the notion of compactness for the goals, where “success can be determined by looking at long but finite prefixes of actual execution.”
As an example application, the author develops a strategy for communicating over a network where the protocol may have changed. The goal here is to allow protocol designers to modify the network protocol and have the users adapt. It is worth noting that if the two users agree on the check-summing process, there is much that they can do in terms of exchanging information. The results demonstrate the possibility of communicating under protocol changes, using a bounded modification weighting scheme to manage the enumeration of choice of strategy [3]. It should be noted that the results depend critically on there being only two users involved. The presence of more users on the network raises major problems related to determining the source of messages.
The book is (necessarily) very densely written, although many of the proofs are preceded by a guide that describes how the proof works, which is helpful. The author claims that a “good undergraduate computational complexity” background is all that is needed of the reader, and while this may be literally true, readers will find it necessary to concentrate to follow the details. The lack of an index makes it hard sometimes to keep track of the definitions. However, the numbering of theorems and the like does mitigate this problem somewhat. The ideas in the book are important and deserve to be well known.
