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

communication complexitydirected acyclic graphmultiprocessingparallel computationtradeoff

Mathematics Subject Classification ID

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

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

(15)

• Trade-offs between communication and space
• Minimizing the schedule length for a parallel 3D-grid precedence graph
• Scheduling task-trees with additive scales on parallel/distributed machines
• Processor-time tradeoffs under bounded-speed message propagation. II: Lower bounds
• Scheduling tree dags on parallel architectures
• The time-identity tradeoff
• Efficient Timing of Communication in Multiperiod Agencies
• scientific article; zbMATH DE number 425387 (Why is no real title available?)
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation
• Some models for scheduling parallel programs with communication delays
• Scheduling task-tree with additive scales on parallel/distributed machines
• 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
• Timing a public information and cost reduction
• Communication complexity of PRAMs

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)