vii. Parallel and Distributed Computing Theory

Constant-factor tricks and SIMD/#pragma tuning squeeze more work out of one core; this note is the theory for when work is genuinely split across many — mostly not contest-actionable directly (judges run single-threaded single-process solutions), but it’s the formal model behind “how many processors would this need” questions, parallel algorithms that do show up in CP as single-threaded simulations (e.g. parallel prefix sums, Boruvka’s MST as a PRAM-style algorithm run sequentially), and distributed-systems framing that occasionally appears in problem statements.

The PRAM model and work-span analysis

A PRAM (Parallel Random Access Machine) is $p$ processors sharing memory, synchronized in lockstep; variants differ in whether concurrent reads/writes to the same address are allowed (EREW/CREW/CRCW — Exclusive/Concurrent Read, Exclusive/Concurrent Write).

Work $W$ = total operations across all processors (what a single-threaded machine would do). Span (depth) $S$ = length of the longest chain of sequentially-dependent operations (the critical path) — the minimum possible running time even with infinitely many processors.

Proof: the work-span bound (Brent's theorem)

With $p$ processors, running time is $\ge \max (W/p,S)$: at least $W/p$ since $p$ processors can do at most $pW/p=W$ work-units of total work in $W/p$ steps, and at least $S$ since the critical path must execute in order regardless of processor count. Brent’s scheduling theorem gives a matching upper bound: a greedy scheduler achieves $T_p\le W/p+S$ (at each of $S$ “rounds,” up to $p$ ready operations run in parallel; summing $\lceil (\text{ready ops in round }i)/p\rceil$ over all rounds telescopes to at most $W/p+S$). So $T_p=\Theta (\max (W/p,S))$ up to that additive slack, and parallel speedup is capped by $S$ no matter how many processors you throw at it — this is why span, not just work, is the quantity to minimize when designing a parallel algorithm. $■$

Algorithm	Work	Span
prefix sum ($n$ elements)	$O(n)$	$O(\log n)$ (Blelloch’s up-sweep/down-sweep)
merge sort	$O(n\log n)$	$O({\log }^{2}n)$
array sum via binary reduction	$O(n)$	$O(\log n)$
sequential loop over $n$ elements	$O(n)$	$O(n)$ — no parallelism available

Parallel prefix sum (Blelloch scan), work $O(n)$, span $O(\log n)$: up-sweep builds a binary tree of partial sums bottom-up ($\log n$ levels, each doing work proportional to the level’s node count — total $O(n)$ by the usual geometric-series argument), down-sweep distributes the prefix values back down. This is the theoretical justification for why a GPU can compute a prefix sum over millions of elements in time logarithmic in $n$ rather than linear, and the same up-sweep/down-sweep shape recurs in parallel segment-tree builds.

Consensus and Byzantine agreement

Problem: $n$ processes, each starting with a value, must agree on a single value despite some processes failing or behaving arbitrarily (Byzantine = actively malicious, not just silent).

Proof: Byzantine consensus is impossible with $n\le 3f$ Byzantine faults

Suppose $n=3f$ exactly and partition the $n$ processes into three groups $A,B,C$ of size $f$ each. If $C$ is the actual set of faulty processes, $C$ can behave toward $A$ exactly as if $B$ were faulty and toward $B$ exactly as if $A$ were faulty — simulating two entirely different “which group is faulty” scenarios simultaneously and consistently, since $A$ and $B$ only have $f$ processes each to cross-check $C$‘s story against, which is exactly what $C$ can fabricate. $A$ and $B$ then cannot distinguish “which group is actually faulty,” so no protocol can guarantee agreement. The classical result (Pease, Shostak, Lamport, 1980) is that $n\ge 3f+1$ processes are both necessary (by the argument above) and sufficient (via an explicit protocol) to tolerate $f$ Byzantine failures. $■$

This "$n\ge 3f+1$" bound is the theoretical ceiling every real Byzantine fault-tolerant system (blockchain consensus protocols included) is built against — it’s the reason “up to $1/3$ of nodes can be malicious” is the standard tolerance figure quoted for BFT systems, not some rounder number.

The MapReduce model

Abstracts distributed computation as map (apply a function independently to each input record, embarrassingly parallel — zero span cost beyond $O(1)$) then shuffle (group intermediate results by key, across machines — the expensive, network-bound step) then reduce (aggregate each key’s group). The model’s entire design is built around making map and reduce trivially parallel while isolating all cross-machine communication into one well-understood shuffle phase.

MapReduce job	Map	Reduce
word count	emit $(word,1)$ per occurrence	sum counts per word
inverted index	emit $(word,docID)$	collect docIDs per word
distributed sort (terasort)	emit $(key,record)$, partitioned by key range	— (shuffle alone sorts, if ranges are disjoint and ordered)
matrix multiplication	emit partial products	sum partial products per output cell

The CP-relevant takeaway is purely conceptual: any problem phrased as “process $N$ independent items, then combine results grouped by some key” is a MapReduce shape, and recognizing that shape is useful even when you’re about to write a single-threaded loop, because it tells you the combine step (reduce) is the only part that needs synchronization — everything else is free to reorder, which is exactly the insight behind small-to-large merging and bucket-based offline techniques.

Related notes

• Fast I/O and Constant Factor — single-core parallelism (SIMD, pragmas) rather than multi-processor.
• Divide and Conquer — the recursion-tree shape that gives most parallel algorithms their logarithmic span.
• Complexity Theory and NP-Hardness — NC and circuit-depth classes are the complexity-theoretic formalization of “span.”