Message Lower Bounds via Efficient Network Synchronization
From MaRDI portal
Publication:2835018
DOI10.1007/978-3-319-48314-6_6zbMath1437.68025OpenAlexW2547779378MaRDI QIDQ2835018
Michele Scquizzato, Gopal Pandurangan, David Peleg
Publication date: 1 December 2016
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-48314-6_6
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)
Related Items (1)
Cites Work
- Unnamed Item
- Tight bounds for distributed minimum-weight spanning tree verification
- Sublinear bounds for randomized leader election
- When distributed computation is communication expensive
- Optimal lower bounds for some distributed algorithms for a complete network of processors
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Toward Optimal Bounds in the Congested Clique
- A tight unconditional lower bound on distributed randomwalk computation
- On the power of the congested clique model
- Trading Bit, Message, and Time Complexity of Distributed Algorithms
- Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
- Design and Analysis of Distributed Algorithms
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- A trade-off between information and communication in broadcast protocols
- Complexity of network synchronization
- Lower bounds on communication complexity in distributed computer networks
- The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Determinism vs. Nondeterminism in Multiparty Communication Complexity
- Distributed Computing: A Locality-Sensitive Approach
- An Optimal Synchronizer for the Hypercube
- Introduction to Distributed Algorithms
- Communication Complexity
- Distributed Verification and Hardness of Distributed Approximation
- A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
- Distributed Computing on Core-Periphery Networks: Axiom-Based Design
- Optimal deterministic routing and sorting on the congested clique
- Distributed Computation of Large-scale Graph Problems
- On the Complexity of Universal Leader Election
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
This page was built for publication: Message Lower Bounds via Efficient Network Synchronization