Dynamic Asymmetric Communication

  • Travis Gagie
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


We present four new asymmetric communication protocols, with which a server with high bandwidth can help clients with low bandwidth send it messages. Three of our protocols are the first to use only a single round of communication for each message. Unlike previous authors, we do not assume the server knows the messages’ distribution.


Single Round Active Client Distribute Source Code Single Client USENIX Security Symposium 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Adler, M.: Collecting correlated information from a sensor network. In: Proceedings of the 16th Symposium on Discrete Algorithms, pp. 479–488 (2005)Google Scholar
  2. 2.
    Adler, M., Demaine, E.D., Harvey, N.J.A., Pǎtraşcu, M.: Lower bounds for asymmetric communication complexity and distributed source coding. In: Proceedings of the 17th Symposium on Discrete Algorithms, pp. 251–260 (2006)Google Scholar
  3. 3.
    Adler, M., Maggs, B.M.: Protocols for asymmetric communication channels. Journal of Computer and System Sciences 64(4), 573–596 (2001)CrossRefMathSciNetGoogle Scholar
  4. 4.
    Bentley, J.L., Sleator, D.D., Tarjan, R.E., Wei, V.K.: A locally adaptive data compression scheme. Communications of the ACM 29(4), 320–330 (1986)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Bose, P., Krizanc, D., Langerman, S., Morin, P.: Asymmetric communication protocols via hotlink assignments. Theory of Computing Systems 36(6), 655–661 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Elias, P.: Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory 21(2), 194–203 (1975)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Feamster, N., Balazinska, M., Harfst, G., Balakrishnan, H., Karger, D.: Infranet: Circumventing web censorship and surveillance. In: Proceedings of the 11th USENIX Security Symposium, pp. 247–262 (2002)Google Scholar
  8. 8.
    Feamster, N., Balazinska, M., Wang, W., Balakrishnan, H., Karger, D.: Thwarting web censorship with untrusted messenger discovery. In: Proceedings of the 3rd International Workshop on Privacy Enhancing Technologies, pp. 125–140 (2003)Google Scholar
  9. 9.
    Gagie, T.: Dynamic Shannon coding. In: Proceedings of the 12th European Symposium on Algorithms, pp. 359–370 (2004)Google Scholar
  10. 10.
    Ghazizadeh, S., Ghodsi, M., Saberi, A.: A new protocol for asymmetric communication channels: Reaching the lower bounds. Scientia Iranica 8(4), 297–302 (2001)Google Scholar
  11. 11.
    Gilbert, E.N., Moore, E.: Variable-length binary encodings. Bell System Technical Journal 38, 933–968 (1959)MathSciNetGoogle Scholar
  12. 12.
    Knuth, D.E.: Dynamic Huffman coding. Journal of Algorithms 6(2), 163–180 (1985)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Laber, E.S., Holanda, L.G.: Improved bounds for asymmetric communication protocols. Information Processing Letters 83(4), 205–209 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27, 379–423 (1948)zbMATHMathSciNetGoogle Scholar
  15. 15.
    Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. Journal of the ACM 32, 652–686 (1985)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Wang, W.: Implementation and security analysis of the Infranet anti-censorship system. Master’s thesis, Massachusetts Institute of Technology (2003)Google Scholar
  17. 17.
    Watkinson, J., Adler, M., Fich, F.: New protocols for asymmetric communication channels. In: Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity, pp. 337–350 (2001)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Travis Gagie
    • 1
  1. 1.Department of Computer ScienceUniversity of TorontoTorontoCanada

Personalised recommendations