Lower bounds for asymmetric communication channels and distributed source coding

ABSTRACT

We prove nearly tight lower bounds on the number of rounds of communication required by efficient protocols over asymmetric channels between a server (with high sending capacity) and one or more clients (with low sending capacity). This scenario captures the common asymmetric communication bandwidth between broadband Internet providers and home users, as well as sensor networks where sensors (clients) have limited capacity because of the high power requirements for long-range transmissions. An efficient protocol in this setting communicates n bits from each of the k clients to the server, where the clients' bits are sampled from a joint distribution D that is known to the server but not the clients, with the clients sending only O(H(D) + k) bits total, where H(D) is the entropy of distribution D. In the single-client case, there are efficient protocols using O(1) rounds in expectation and O(lg n) rounds in the worst case. We prove that this is essentially best possible: with probability 1/2^{O(t lg t)}, any efficient protocol can be forced to use t rounds. In the multi-client case, there are efficient protocols using O(lg k) rounds in expectation. We prove that this is essentially best possible: with probability Ω(1), any efficient protocol can be forced to use Ω(lg k/ lg lg k) rounds. Along the way, we develop new techniques of independent interest for proving lower bounds in communication complexity.

REFERENCES

• 1: Micah Adler, Collecting correlated information from a sensor network, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: Anne Aaron , Bernd Girod, Compression with Side Information Using Turbo Codes, Proceedings of the Data Compression Conference (DCC '02), p.252, April 02-04, 2002
• 3: Micah Adler , Bruce M. Maggs, Protocols for asymmetric communication channels, Journal of Computer and System Sciences, v.63 n.4, p.573-596, December 2001 [doi>10.1006/jcss.2001.1779]
• 4: J. Bajcsy and P. Mitran, Coding for the Slepian- Wolf problem with turbo codes, Proc. GlobeCom 2001.
• 5: P. Bose, D. Krizanc, S. Langerman, and P. Morin, Asymmetric communication protocols via hotlink assignments, Theory of Computing Systems 36(6): 655--661, 2003. Special issue dedicated to the IXth International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002).
• 6: Amit Chakrabarti , Oded Regev, An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.473-482, October 17-19, 2004 [doi>10.1109/FOCS.2004.12]
• 7: J. Chou, D. Petrovic, and K. Ramchandran, A Distributed and Adaptive Signal Processing Approach to Reducing Energy Consuumption in Sensor Networks, Proc. INFOCOM 2003.
• 8: Todd P. Coleman , Anna H. Lee , Muriel Médard , Michelle Effros, On Some New Approaches to Practical Slepian-Wolf Compression Inspired by Channel Coding, Proceedings of the Conference on Data Compression, p.282, March 23-25, 2004
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: Nick Feamster , Magdalena Balazinska , Greg Harfst , Hari Balakrishnan , David Karger, Infranet: Circumventing Web Censorship and Surveillance, Proceedings of the 11th USENIX Security Symposium, p.247-262, August 05-09, 2002
• 11: L. M. Feeney and M. Nilsson, Investigating the energy consumption of a wireless network interface in an ad hoc network, Proc. INFOCOM 2001.
• 12: J. Garcia-Frias and Y. Zhao, Compression of correlated binary sources using turbo codes, IEEE Communications Letters 5(10): 417--419, Oct 2001.
• 13: J. Garcia-Frias and W. Zhong, LDPC codes for compression of multiterminal sources with hidden Markov correlation, IEEE Communications Letters 7(3): 115--117, Mar 2003.
• 14: S. Ghazizadeh, M. Ghodsi, and A. Saberi, A New Protocol for Asymmetric Communication Channels, Reaching Lower Bounds, Scientia Iranica 8(4), 2001.
• 15: Eduardo Sany Laber , Leonardo Gomes Holanda, Improved bounds for asymmetric communication protocols, Information Processing Letters, v.83 n.4, p.205-209, 31 August 2002 [doi>10.1016/S0020-0190(01)00332-5]
• 16: D. A. Huffman, A method for the construction of minimum redundancy codes, Proc. IRE 40(10): 1099--1101, 1952.
• 17: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 18: Ching-Fu Lan , Angelos D. Liveris , Krishna Narayanan , Zixiang Xiong , Costas Georghiades, Slepian-Wolf Coding of Multiple M-ary Sources Using LDPC Codes, Proceedings of the Conference on Data Compression, p.549, March 23-25, 2004
• 19: Angelos D. Liveris , Zixiang Xiong , Costas N. Georghiades, Distributed Compression of Binary Sources Using Conventional Parallel and Serial Concatenated Convolutional Codes, Proceedings of the Conference on Data Compression, p.193, March 25-27, 2003
• 20: A. Liveris, Z. Xiong and C. Georghiades, Compression of binary sources with side information at the decoder using LDPC codes, IEEE Communications Letters 6(10): 440--442, Oct 2002.
• 21: A. Liveris, C. Lan, K. Narayanan, Z. Xiong, and C. Georghiades, Slepian-Wolf coding of three binary sources using LDPC codes, Proc. Intl. Symp. Turbo Codes and Related Topics 2003.
• 22: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 23: S. Pradhan, J. Kusuma, and K. Ramchandran, Distributed compression in a dense microsensor network, IEEE Signal Processing Mag., 19: 51--60, Mar 2002.
• 24: D. Schonberg, S. Pradhan, and K. Ramchandran, Distributed code constructions for the entire Slepian-Wolf rate region for arbitrarily correlated sources, Proc. DCC 2004.
• 25: P. Sen, Lower bounds for predecessor searching in the cell probe model, Proc. 18th IEEE Conference on Computational Complexity (CCC) 2003.
• 26: C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27: 379--423 and 623--656, 1948.
• 27: D. Slepian and J. K. Wolf, Noiseless encodings of correlated information sources, IEEE Trans. on Information Theory, IT-19: 471--480, July 1973.
• 28: Vladimir Stankovic , Angelos D. Liveris , Zixiang Xiong , Costas N. Georghiades, Design of Slepian-Wolf Codes by Channel Code Partitioning, Proceedings of the Conference on Data Compression, p.302, March 23-25, 2004
• 29: John Watkinson, New Protocols for Asymmetric Communication Channels, Master's Thesis, U. Toronto, 2000.
• 30: John Watkinson, Micah Adler, and Faith Fich, New Protocols for Asymmetric Communication Channels, Proc. 8th Intl. Colloquium on Structural Information and Communication Complexity (SIROCCO) 2001.
• 31: Zixiang Xiong, Angelos D. Liveris, and Samuel Cheng, Distributed Source Coding for Sensor Networks, IEEE Signal Processing Magazine, Sep 2004.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Theory