Protocols for Asymetric Communication Channels
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
This paper examines the problem of communicating an n-bit data item from a client to a server, where the data is drawn from a distribution D that is known to the server but not to the client. Since this question is motivated by asymmetric communication channels, our primary goal is to limit the number of bits transmitted by the client. We present several protocols in which the expected number of bits transmitted by the server and client are On and OHD, respectively, where HD is the entropy of D, and can thus be significantly smaller than n. Shannons Theorem implies that these protocols are optimal in terms of the number of bits sent by the client. The expected number of rounds of communication between the server and client in the simplest of our protocols is OHD. We also give a protocol for which the expected number of rounds is only O1, but which requires more computational effort on the part of the server. A third protocol provides a tradeoff between the computational effort and the number of rounds. These protocols are complemented by several lower bounds and impossibility results. We show that all of our protocols are existentially optimal in terms of the number of bits sent by the server, i.e., there are distributions for which the total number of bits exchanged has to be at least n-1. In addition, we show that there is no protocol that is optimal for every distribution as opposed to just existentially optimal in terms of bits sent by the server. We demonstrate this by proving that it is undecidable to compute, for an arbitrary distribution D, the minimum expected total number of bits sent by the server and client. Furthermore, the problem remains undecidable even if only an approximate solution is required, for any reasonable degree of approximation.
- Computer Systems