Message lower bounds via efficient network synchronization

DOI10.1016/j.tcs.2018.11.017zbMath1437.68026OpenAlexW2903448613WikidataQ128876753 ScholiaQ128876753MaRDI QIDQ2292919

Gopal Pandurangan, David Peleg, Michele Scquizzato

Publication date: 6 February 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.11.017

zbMATH Keywords

lower boundsdistributed algorithmscommunication complexitysynchronizerssynchronous message-passing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight bounds for distributed minimum-weight spanning tree verification
• Sublinear bounds for randomized leader election
• Distributed algorithms for selection in sets
• On the distributional complexity of disjointness
• Practical uses of synchronized clocks in distributed systems
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• 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
• Message Lower Bounds via Efficient Network Synchronization
• Distributed Minimum Cut Approximation
• A tight unconditional lower bound on distributed randomwalk computation
• On the power of the congested clique model
• Communication complexity of approximate matching in distributed graphs
• Trading Bit, Message, and Time Complexity of Distributed Algorithms
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Optimal Distributed Algorithms for Sorting and Ranking
• 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
• The complexity of sorting on distributed systems
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Complexity of network synchronization
• Lower bounds on communication complexity in distributed computer networks
• Electing a leader in a synchronous ring
• 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
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
• Silence-Based Communication
• 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
• Distributed construction of purely additive spanners

This page was built for publication: Message lower bounds via efficient network synchronization