A Communication-Time Tradeoff

DOI10.1137/0216044MaRDI QIDQ3795227zbMATH OpenOpenAlexFDO

Authors Jeffrey D. Ullman, Christos Papadimitriou

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216044

zbMATH Keywords

directed acyclic graphparallel computationtradeoffcommunication complexitymultiprocessing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)

Recommendations

• scientific article; zbMATH DE number 4060722
• Trade-offs between communication and space
• Communication vs. computation
• Automata, Languages and Programming
• Communication complexity of PRAMs

Cited in

(14)

• Scheduling task-trees with additive scales on parallel/distributed machines
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation
• Timing a public information and cost reduction
• Some models for scheduling parallel programs with communication delays
• The time-identity tradeoff
• Scheduling task-tree with additive scales on parallel/distributed machines
• Minimizing the schedule length for a parallel 3D-grid precedence graph
• Communication complexity of PRAMs
• Efficient Timing of Communication in Multiperiod Agencies
• scientific article; zbMATH DE number 425387 (Why is no real title available?)
• Trade-offs between communication and space
• Scheduling tree dags on parallel architectures
• Ofelimos: combinatorial optimization via proof-of-useful-work. A provably secure blockchain protocol
• Optimal parallel execution of complete binary trees and grids into most popular interconnection networks

This page was built for publication: A Communication-Time Tradeoff

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