Large parallel machines can be extremely slow for small problems

DOI10.1007/BF01759055zbMath0729.68019MaRDI QIDQ807013

Vince Grolmusz

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

parallel computationlower boundsfault tolerant computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items

Processor-time tradeoffs in PRAM simulations

Cites Work

• Incomparability in parallel computation
• Simulations among concurrent-write PRAMs
• Parallel computation and conflicts in memory access
• Simulation of Parallel Random Access Machines by Circuits
• Parity, circuits, and the polynomial-time hierarchy
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• The Complexity of Parallel Sorting
• The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
• A universal interconnection pattern for parallel computers