Graph Processing Frameworks

• e.g. Pregel (Google), Apache Giraph (Hadoop), Spark GraphX

The above frameworks are for the bulk-synchronous parallel programming model (BSP).

Vertex Centric Programming

The Vertex Centric Programming Model is one in which:

• Logic is written from the perspective of a single vertex
• Code is executed on all vertices
• Vertices know about:
  • Their own value(s)
  • Outgoing edges

In BSP model, synchronization is essentially a shuffle - must collect pending messages for neighbors in other partitions.

For each vertex in the vertex-centric programming model:

• Superstep 0 ⇒ all vertices are in active state

• Vertex can deactivate itself by voting to halt

• A vertex can be reactivated by receiving an external message

• Algorithm termination is based on all vertices voting to halt

• e.g. Finding the largest value in a graph: