- Protocols for Asymmetric Communication
Channels. M. Adler and B. M. Maggs.
Proceedings of the 39th Annual Symposium on Foundations of
Computer Science (FOCS), October 1998, to appear.
In this paper we examine the problem of sending an n-bit data item
from a client to a server across an asymmetric communication channel.
We demonstrate that there are 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, we assume that the data item is drawn from a probability
distribution D that is known to the server but not to the client.
We present several protocols 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 (and can range
from 0 to n). These protocols are within a small constant factor
of 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 O(H(D)). We also give a
protocol for which the expected number of rounds is only O(1), but
which requires more computational effort on the part of the server. A
third technique provides a tradeoff between the computational effort
and the number of rounds. These protocols are complemented by several
lower bounds and impossibility results. We demonstrate 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. 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 (even approximately), for an arbitrary distribution D, how
many expected bits must be exchanged by the server and client on the
- Back to other
- Back to my home page