Accession Number : ADA333259

Title :   Protocols for Asymetric Communication Channels

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s) : Adler, Micah ; Maggs, Bruce M.

PDF Url : ADA333259

Report Date : DEC 1997

Pagination or Media Count : 25

Abstract : 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 O(n) and O(H(D)), respectively, where H(D) is the entropy of D, and can thus be significantly smaller than n. Shannon's 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 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 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.

Descriptors :   *COMPUTER COMMUNICATIONS, *CLIENT SERVER SYSTEMS, OPTIMIZATION, DATA MANAGEMENT, INFORMATION EXCHANGE, DISTRIBUTED DATA PROCESSING, LOCAL AREA NETWORKS, DATA RATE, TRADE OFF ANALYSIS, DOWNLINKS, UPLINKS.

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE