A trade-off between information and communication in broadcast protocols
From MaRDI portal
Publication:3474265
DOI10.1145/77600.77618zbMath0696.68020OpenAlexW1976485065MaRDI QIDQ3474265
Ronen Vainish, Oded Goldreich, Baruch Awerbuch, David Peleg
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/77600.77618
lower boundsnetwork protocolsbroadcastmessage complexitycomputer-communication networksresource trade-offs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of software (68N99)
Related Items (33)
Energy-Optimal Broadcast in a Tree with Mobile Agents ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Compact routing messages in self-healing trees ⋮ Communication costs in a geometric communication network ⋮ Deterministic broadcasting time with partial knowledge of the network. ⋮ Messy broadcasting - decentralized broadcast schemes with limited knowledge ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? ⋮ Distributed CONGEST Algorithms against Mobile Adversaries ⋮ Improved Tradeoffs for Leader Election ⋮ Broadcasting in geometric radio networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Local Maps: New Insights into Mobile Agent Algorithms ⋮ Assigning labels in an unknown anonymous network with a leader ⋮ Interval routing schemes allow broadcasting with linear message-complexity ⋮ Deterministic broadcasting in ad hoc radio networks ⋮ Hundreds of impossibility results for distributed computing ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Efficient communication in unknown networks ⋮ A \(2\cdot | E |\)-bit distributed algorithm for the directed Euler trail problem ⋮ Trade-offs between the size of advice and broadcasting time in trees ⋮ Communication algorithms with advice ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Topology recognition and leader election in colored networks ⋮ Message lower bounds via efficient network synchronization ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Asynchronous Broadcasting with Bivalent Beeps ⋮ Time-Efficient Broadcast in Radio Networks ⋮ Energy-optimal broadcast and exploration in a tree using mobile agents ⋮ On the Complexity of Universal Leader Election ⋮ Sense of direction in distributed computing ⋮ Convergecast and broadcast by power-aware mobile agents
This page was built for publication: A trade-off between information and communication in broadcast protocols
