Protocols for asymmetric communication channels

The problem of sending an n-bit data item from a client to a server across a asymmetric communication channel is investigated. The scenarios in which a high-speed link from the server to the client can be used to greatly reduce the number of bits sent from the client to the server across a slower link. In particular, it is assumed that the data item is drawn from a probability distribution D that is known to the server but not to the client. Several protocols are presented in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)+1) respectively, where H(D) is the binary entropy of D. These protocols are within a small constant factor of optimal in terms of the number of bits sent by the client.

Duke Scholars

Author Bruce Maggs Computer Science