Lower bounds on communication complexity in distributed computer networks

DOI10.1145/31846.32978zbMath0629.68024OpenAlexW2035038579MaRDI QIDQ3766832

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

parallelismasynchronycommuncication

Mathematics Subject Classification ID

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

Related Items

The Range of Topological Effects on Communication ⋮ Proof labeling schemes ⋮ Deterministic communication complexity of set intersection ⋮ Communication complexity of multi-processor systems ⋮ Communication complexity of PRAMs ⋮ Edge-pancyclicity and path-embeddability of bijective connection graphs ⋮ Trade-offs between communication and space ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Exact communication costs for consensus and leader in a tree