ON INTERACTIVE COMMUNICATION

Almost two decades ago Ahlswede introduced an abstract correlated sour ce (V x W, S) with outputs (v, w) is an element of S subset of v x W, where persons P-V and P-W observe v and w, respectively. More recently , Orlitsky considered the minimal number C-m of bits to be transmitted in m rounds to ''inform P-W about v over one channel.'' He showed tha t C-2 less than or equal to 4C(infinity)+3 and that in general C-2 not similar to C-infinity. We give a simple example for C-3 not similar t o C-infinity. However, for the new model ''inform Pw over two channels ,'' four rounds are optimal for this example-a result we conjecture in general. If both P-V and P-W are to be informed over two channels abo ut the other outcome, we determine asymptotically the complexities for all sources. In our last model ''inform P-V and P-W over one channel' ' for all sources the total number T-2 of required bits is known asymp totically and T-infinity is bounded from below in terms of average deg rees. There are exact results for several classes of regular sources. An attempt is made to discuss the methods of the subject systematicall y.