Graph processing consists of a sequence of discrete iterations separated by a global synchronization barrier. This barrier prevents any vertex from starting its next iteration until all vertices have finished the current iteration.
A graph function is written from the perspective of a single vertex. At each iteration, a vertex receives vertex messages sent from other vertices during the previous iteration, performs a local computation potentially modifying its local state, and might send vertex messages bound for other vertices at the next iteration.
Messages are typically sent along an edge (for example, from the source vertex to the destination vertex of the edge). However, this is not required. A message can be sent to any known target vertex.
A vertex can alter the course of graph processing in the following ways:
- It might elect to become inactive. An inactive vertex does not participate in future iterations unless it receives new messages.
- It can issue a local halt (localHalt). A vertex that issues a localHalt does not to participate in future iterations, even if it receives new messages.
- It can issue a global halt (globalHalt) that stops graph processing altogether.
Graph processing is halted naturally at the end of an iteration if no messages are sent within that iteration, or if all messages that are sent within that iteration are addressed to vertices that have called localHalt() and therefore are no longer responding to messages.
Global halt is responded to after the current iteration completes. That is, even though global halt is signaled by one or more vertices, all vertices get a chance to complete the current iteration, including updates to the vertex state and local aggregators. Moreover, local aggregator updates are rolled up into final global values before graph processing finally responds to the global halt by moving into the last phase where final results are emitted.
For example, you can start an operation, such as a search, at one vertex, and then pass one or more messages to "downstream" vertices (the vertices that this vertex has edges pointing to). Each downstream vertex may then pass a message on to its downstream vertices. Typically, each iteration involves receiving one set of 0 or more messages, doing some processing, and then optionally sending messages.