Message Lower Bounds via Efficient Network Synchronization

DOI10.1007/978-3-319-48314-6_6MaRDI QIDQ2835018zbMATH OpenOpenAlexFDO

Authors Gopal Pandurangan, Michele Scquizzato, 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

Mathematics Subject Classification ID

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

Recommendations

• Message lower bounds via efficient network synchronization
• scientific article; zbMATH DE number 4050994
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation
• Message and time efficient consensus protocols for synchronous distributed systems
• Efficient perfectly secure message transmission in synchronous networks
• Lower bounds on communication complexity in distributed computer networks
• Message-optimal protocols for Byzantine Agreement
• Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols
• Lower bounds on communication overlap of networks

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A tight unconditional lower bound on distributed randomwalk computation
• A trade-off between information and communication in broadcast protocols
• An Optimal Synchronizer for the Hypercube
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Communication Complexity
• Complexity of network synchronization
• Design and Analysis of Distributed Algorithms
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• Distributed Computing: A Locality-Sensitive Approach
• Distributed computation of large-scale graph problems
• Distributed computing on core-periphery networks: axiom-based design
• Distributed verification and hardness of distributed approximation
• Introduction to Distributed Algorithms
• Lower bounds on communication complexity in distributed computer networks
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On the Complexity of Universal Leader Election
• On the power of the congested clique model
• Optimal deterministic routing and sorting on the congested clique
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Toward optimal bounds in the congested clique, graph connectivity and MST
• Trading bit, message, and time complexity of distributed algorithms

Cited in

(3)

• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Message lower bounds via efficient network synchronization

This page was built for publication: Message Lower Bounds via Efficient Network Synchronization

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