GPS: A Graph Processing System

Overview

In systems such as GPS and Pregel, the input graph (directed, possibly with values on edges) is distributed across machines and vertices send each other messages to perform a computation. Computation is divided into iterations called supersteps. Analogous to the map() and reduce() functions of the MapReduce framework, in each superstep a user-defined function called vertex.compute() is applied to each vertex in parallel. The user expresses the logic of the computation by implementing vertex.compute(). This design is based on Valiant's Bulk Synchronous Parallel model of computation. A detailed description can be found in the original Pregel paper.

There are three main differences between Pregel and GPS:

• GPS is open-source.
• GPS extends Pregel's API with a master.compute() function, which enables easy and efficient implementation of algorithms that are composed of multiple vertex-centric computations, combined with global computations.
• GPS has an optional dynamic repartitioning scheme, which reassigns vertices to different machines during graph computation to improve performance, based on observing communication patterns.

Using GPS we have studied the effects on system performance of different ways of partioning the graph, both before the graph computation starts and during the computation. A detailed description of GPS and our work on partitioning can be found in our online technical report.

The GPS project is supported by the National Science Foundation (grant IIS-0904497), KAUST, and an Amazon Web Services Research Grant.

The GPS source code is available as open-source code under the BSD license. The source code can be found here. We will provide full documentation on how to download, program, and run GPS in early July 2012. If you want to use GPS before then, please email semih @ stanford.edu.