Pregel-style message passing
Pregel-style message passing refers to a graph-computation execution model popularized by Google’s Pregel system, where computation proceeds in synchronized rounds called supersteps.
The model in one sentence
In each superstep, every active vertex runs the same “compute” function in parallel, reads the messages it received from the previous superstep, sends messages to other vertices, then everyone hits a barrier synchronization; messages are delivered in the next superstep.
Key mechanics
Vertex-centric computation The program is written as: compute(vertex_state, incoming_messages) → (updated_state, outgoing_messages). Each vertex only “sees” its own state + its inbox for this step.
Bulk Synchronous Parallel (BSP)
Each superstep is: Compute phase: all active vertices execute (conceptually in parallel). Communication phase: vertices emit messages to neighbors. Barrier / sync: system waits until all are done. Delivery: messages become available at the start of the next superstep.
Deterministic “next-step” visibility
Messages sent in superstep k are not visible until superstep k+1.
This avoids race conditions you’d get from fully asynchronous message passing.
Halting / inactivity
A vertex can “vote to halt” (become inactive) and only re-activates if it receives a message later.
Tiny example intuition
Imagine shortest-path:
- Superstep 0: the source vertex sends “distance=0” to its neighbors.
- Superstep 1: neighbors update their distance and forward improved distances.
- Repeat until no one improves anything.