GatherApplyScatter

Gather-Apply-Scatter (GAS) is a vertex-centric model for graph computation that structures iterative updates around individual vertices. It originated with the GraphLab framework as a core execution pattern for scalable graph analytics, and it has influenced several subsequent systems and APIs. In GAS, computation at each active vertex proceeds through three phases in each iteration: Gather, Apply, and Scatter.

During Gather, a vertex collects information from its incident edges or neighboring vertices to form a local aggregate, or gather value. This step may read edge data and neighbor states without directly mutating them. In Apply, the vertex uses the gathered information to update its own state, producing a new local value or a partial update to its state. Finally, in Scatter, the vertex propagates effects of its updated state to its neighbors, typically by scheduling neighbor actions or sending messages that will trigger their own Gather-Apply steps in the next phase of execution.

GAS can be executed synchronously or asynchronously, depending on the system configuration. Synchronous execution advances in lockstep through iterations, while asynchronous or semi-synchronous variants allow overlapping computation and communication, potentially accelerating convergence on certain workloads. The model is well suited for iterative graph algorithms such as PageRank, single-source shortest paths, connected components, and various forms of label propagation, where locality and controlled data flow are advantageous.

Limitations include implementation complexity and the need to manage data races or inconsistencies in asynchronous settings. Nonetheless, GAS remains a foundational concept in graph processing, offering a clear separation of data gathering, local state updates, and neighbor-directed propagation.