Lower bounds on communication complexity in distributed computer networks

DOI10.1145/31846.32978MaRDI QIDQ3766832zbMATH OpenOpenAlexFDO

Authors Prasoon Tiwari

Publication date 1987

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/31846.32978

zbMATH Keywords

asynchronycommuncicationparallelism

Mathematics Subject Classification ID

Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Lower bounds on communication complexity
• Two lower bounds in asynchronous distributed computation
• scientific article; zbMATH DE number 6691438
• On the message complexity of distributed problems

Cited in

(24)

• Lower bounds on communication overlap of networks
• Bit complexity of order statistics on a distributed star network
• Communication complexity of multi-processor systems
• Trade-offs between communication and space
• The communication complexity of computing differentiable functions in a multicomputer network
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Exact communication costs for consensus and leader in a tree
• Deterministic communication complexity of set intersection
• Lower bounds for in-network computation of arbitrary functions
• Message lower bounds via efficient network synchronization
• Proof labeling schemes
• Edge-pancyclicity and path-embeddability of bijective connection graphs
• Message Lower Bounds via Efficient Network Synchronization
• scientific article; zbMATH DE number 6691438 (Why is no real title available?)
• The Range of Topological Effects on Communication
• Amortized Communication Complexity of Distributions
• scientific article; zbMATH DE number 4011939 (Why is no real title available?)
• scientific article; zbMATH DE number 528937 (Why is no real title available?)
• Tight Network Topology Dependent Bounds on Rounds of Communication
• The Communication Complexity of Distributed epsilon-Approximations
• Communication lower bounds using directional derivatives
• Average and Randomized Complexity of Distributed Problems
• The message complexity of distributed graph optimization
• Communication complexity of PRAMs

This page was built for publication: Lower bounds on communication complexity in distributed computer networks

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