Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Pregel, BSP and iterative algorithms

How does batching by round replace locality, and what does each round cost?

Pregel / BSP: batching by round

The problem stated at the top was that you cannot batch by address. (Google's graph system) answers by no longer trying.

Express the computation from one vertex's point of view: each vertex receives messages, updates its own state, and sends messages along its edges. Then run it in . In each superstep, every vertex processes the messages from the previous round; all messages created this round are delivered together; and a global barrier (everyone waits until everyone has finished) separates the rounds. This model is called (Bulk Synchronous Parallel). One superstep corresponds to one hop.

What this buys is precise. All the random access in a round becomes one all-to-all shuffle of messages: a distributed redistribution of data in which every worker sends data to every other worker, grouped by destination. A shuffle is sequential, batchable and compressible. Messages to the same destination vertex can be merged by a (a function that pre-aggregates messages before sending, such as keeping only the minimum). That is partial aggregation, the same trick a distributed GROUP BY uses. Unpredictable fine-grained pointer chasing has been converted into coarse bulk data movement.

The price is equally precise: a global barrier per hop. The cost of a round is now the maximum over workers, not the average. So straggler effects (the slowest worker holds everybody up) apply at full strength once per superstep. The tail-latency arithmetic of is paid k times. A hub vertex receiving millions of messages is the straggler, which is why vertex-cut and combiners are not optional extras. They are what makes BSP work at all.

This rule applies well beyond graphs:

Micro-batching in streaming does this. Group commit (many transactions share one disk flush) does this. Vectorized execution does this inside one operator. Deferred index maintenance does this. The common price is always the same: latency is quantized to the round, and the round costs the slowest participant.

The asynchronous alternative has no barrier: vertices update whenever their neighbours change. It removes the straggler tax and typically needs fewer effective updates, because information can travel faster than one hop per round. It pays in non-determinism (results can differ between runs), harder termination detection, and much harder fault recovery, because there is no clean global state to checkpoint (to save for restart). Which one wins is workload-dependent and genuinely unsettled. The barrier's real advantage is operational simplicity, not performance, and that is a legitimate reason to choose it.

One line: BSP converts unpredictable pointer chasing into one shuffle per hop, and pays a global barrier and a straggler tax per round.

PageRank and connected components as iterative dataflow

Both are fixpoint computations: apply a transformation repeatedly until the state stops changing.

  • PageRank gives each vertex an importance score. Each round, a vertex sends its score along its edges, and each vertex sums what it receives and renormalizes.
  • Connected components finds groups of vertices that can reach each other. Each round, a vertex sends its label (an id), and each vertex keeps the minimum label it sees.

They are structurally identical: a per-vertex aggregate over incoming messages, a per-vertex update, repeat. Three mechanisms matter, and none of them is specific to graphs.

Termination is a distributed problem, not a local one. You stop when no vertex changed, which needs a global aggregate every round. Each iteration therefore costs a synchronization round on top of the work. This is why iteration counts are usually capped in practice, and convergence is declared by a threshold ("changes smaller than 0.0001") instead of by exactness. It is a coordination cost, charged per iteration.

The two examples have different convergence character, and this is not accidental. PageRank converges geometrically (each round shrinks the error by a constant factor), so it can be truncated at a fixed iteration count. The answer is a real-valued approximation, and nobody can tell 20 iterations from 30. must run until nothing changes, because a label that has not yet propagated is not an approximate answer, it is a wrong one. Its iteration count depends on the graph's diameter (the longest shortest path), which is data-dependent. Approximable and non-approximable iterative computations have completely different cost predictability. This is the one-sided rule again: where an exact answer is owed, an approximation cannot simply be truncated.

The dominant optimization is doing less work per round. Most vertices stop changing early, so only active vertices should send messages. Incremental and differential approaches generalize this: recompute only what a change actually affects. Graph is where incremental processing has its strongest justification, because the alternative is re-running a k-round global shuffle to absorb one new edge.

One line: iterative graph computation is fixpoint dataflow. Its cost is set by whether the answer can be truncated and by how quickly the active set shrinks.