Parallel and Distributed Algorithms
Computation Beyond One Processor
Scope
Parallel and distributed algorithms study how to split work across multiple processors or machines while managing communication, synchronization, and failure. Scalability depends on both asymptotic work and coordination overhead.
Core Metrics
In parallel algorithm analysis, what does span measure?
Span is the longest chain of dependent operations and bounds parallel time.
Correct answer: The critical path length
Why can communication dominate in distributed algorithms?
Network latency and bandwidth limits can outweigh raw compute speed.
Correct answer: Because moving data between machines is often much slower than local computation.
Parallel vs. Distributed Perspectives
Parallel computing
- Often shared-memory or tightly coupled
- Focuses on synchronization and cache effects
- Optimizes work and span
Distributed computing
- Often message-passing across machines
- Focuses on communication and fault tolerance
- Optimizes locality and network usage
Designing a Parallel Algorithm
-
1
Identify independent subproblems or associative operations.
-
2
Minimize synchronization and contention.
-
3
Balance load across processors.
-
4
Analyze work, span, and communication costs.
-
5
Validate correctness under the target memory or network model.
Which property is most important for efficient parallel reduction?
Associativity allows partial results to be combined in any tree shape.
Correct answer: Associativity
Concurrency Hazard
Race conditions and deadlocks can invalidate an otherwise correct algorithmic idea if synchronization is not designed carefully.
Modern Context
Contemporary systems range from multicore CPUs and GPUs to clusters and serverless environments. The best algorithms exploit the hierarchy of parallelism while respecting bottlenecks like memory bandwidth, synchronization, and stragglers.