Document Open Access Logo

Streaming Communication Protocols

Authors Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.130.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Lucas Boczkowski
Iordanis Kerenidis
Frédéric Magniez

Cite As Get BibTex

Lucas Boczkowski, Iordanis Kerenidis, and Frédéric Magniez. Streaming Communication Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 130:1-130:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.130

Abstract

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. Input arrives as a stream, spread between several agents across a network. Each agent has a bounded memory, which can be updated upon receiving a new bit, or a message from another agent. We provide tight tradeoffs between the necessary resources, i.e. communication between agents and memory, for some of the canonical problems from communication complexity by proving a strong general lower bound technique. Second, we analyze the Approximate Matching problem and show that the complexity of this problem (i.e. the achievable approximation ratio) in the one-way variant of our model is strictly different both from the streaming complexity and the one-way communication complexity thereof.

Subject Classification

Keywords
  • Networks
  • Communication Complexity
  • Streaming Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137-147, 1999. Google Scholar
  2. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms, pages 1345-1364, 2016. Google Scholar
  3. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In Proceedings of the 27th IEEE Foundations of Computer Science, pages 337-347, 1986. Google Scholar
  4. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004. Google Scholar
  5. Paul Beame, Martin Tompa, and Peiyuan Yan. Communication-space tradeoffs for unrestricted protocols. In Proceedings of 31st Foundations of Computer Science, pages 420-428, 1990. Google Scholar
  6. Therese C. Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov. Tight bounds on maximal and maximum matchings. Discrete Mathematics, 285(1-3):7-15, 2004. Google Scholar
  7. Joshua E. Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, and Xiaoming Sun. Space-bounded communication complexity. In Proceedings of the 4th Innovations in Theoretical Computer Science, pages 159-172, 2013. Google Scholar
  8. Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, and Hing-Fung Ting. Continuous monitoring of distributed data streams over a time-based sliding window. Algorithmica, 62(3):1088-1111, 2011. Google Scholar
  9. Graham Cormode and Minos N. Garofalakis. Sketching streams through the net: Distributed approximate query tracking. In International Conference on Very Large Data Bases, pages 13-24, 2005. Google Scholar
  10. Graham Cormode, Minos N. Garofalakis, S. Muthukrishnan, and Rajeev Rastogi. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In Special Interest Group on Management of Data, pages 25-36, 2005. Google Scholar
  11. Graham Cormode, S. Muthukrishnan, and Ke Yi. Algorithms for distributed functional monitoring. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, pages 1076-1085, 2008. Google Scholar
  12. Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. Continuous sampling from distributed streams. J. ACM, 59(2):10:1-10:25, 2012. Google Scholar
  13. Graham Cormode, S. Muthukrishnan, and Wei Zhuang. What’s different: Distributed, continuous monitoring of duplicate-resilient aggregates on data streams. In Proceedings of the 22nd International Conference on Data Engineering, page 57, 2006. Google Scholar
  14. Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. On the complexity of processing massive, unordered, distributed data. CoRR, abs/cs/0611108, 2006. Google Scholar
  15. Phillip B. Gibbons and Srikanta Tirthapura. Estimating simple functions on the union of data streams. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 281-291, 2001. Google Scholar
  16. Phillip B. Gibbons and Srikanta Tirthapura. Distributed streams algorithms for sliding windows. In Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures, pages 63-72, 2002. Google Scholar
  17. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the 23d ACM-SIAM Symposium on Discrete Algorithms, pages 468-485, 2012. Google Scholar
  18. Zengfeng Huang, Ke Yi, and Qin Zhang. Randomized algorithms for tracking distributed count, frequencies, and ranks. In Proceedings of the 31st Symposium on Principles of Database Systems, pages 295-306, 2012. Google Scholar
  19. Russell Impagliazzo and Ryan Williams. Communication complexity with synchronized clocks. In Proceedings of the 25th IEEE Conference on Computational Complexity, pages 259-269, 2010. Google Scholar
  20. Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms, pages 1679-1697, 2013. Google Scholar
  21. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 734-751, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.55.
  22. Christian Konrad. Maximum matching in turnstile streams. In Proceedings of 23rd European Symposium on Algorithms, pages 840-852, 2015. Google Scholar
  23. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  24. Tak Wah Lam, Prasoon Tiwari, and Martin Tompa. Trade-offs between communication and space. Journal of Computer and System Sciences, 45(3):296-315, 1992. Google Scholar
  25. Yi Li, Huy L. Nguyen, and David P. Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Proceedings of the 46th ACM Symposium on Theory of Computing, pages 174-183, 2014. Google Scholar
  26. Zhenming Liu, Bozidar Radunovic, and Milan Vojnovic. Continuous distributed counting for non-monotonic streams. In Proceedings of the 31st ACM Symposium on Principles of Database Systems, pages 307-318, 2012. Google Scholar
  27. S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 2(1):117-236, 2005. Google Scholar
  28. David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the 44th ACM Symposium on Theory of Computing, pages 941-960, 2012. Google Scholar
  29. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In Proceedings of the 11th ACM Symposium on Theory of Computing, pages 209-213, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact