Streaming Communication Protocols

DOI10.1145/3276748zbMATH Open1442.68012arXiv1609.07059OpenAlexW2962923964MaRDI QIDQ5205801FDOQ5205801

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

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents are allowed to communicate with each other and also update their memory based on the input bit they read and the previous message they received. We provide tight tradeoffs between the necessary resources, i.e. communication 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.

Full work available at URL: https://arxiv.org/abs/1609.07059

Recommendations

• Streaming communication protocols
• scientific article; zbMATH DE number 772001
• Transmission Protocols for Instruction Streams
• Broadcasting buffering communication

zbMATH Keywords

approximate matchingcommunication complexitynetwork protocolsstreaming algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Network protocols (68M12)

Cited In (2)

• Streaming communication protocols
• Title not available (Why is that?)

This page was built for publication: Streaming Communication Protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205801)