Think Sequential, Run Parallel

Parallel computation is often a must when processing large-scale graphs. However, it is nontrivial to write parallel graph algorithms with correctness guarantees. This paper presents the programming model of \(\mathsf {GRAPE}\), a parallel GRAPh Engine [19]. \(\mathsf {GRAPE}\) allows users to “plug in” sequential (single-machine) graph algorithms as a whole, and it parallelizes the algorithms across a cluster of processors. In other words, it simplifies parallel programming for graph computations, from think parallel to think sequential. Under a monotonic condition, it guarantees to converge at correct answers as long as the sequential algorithms are correct. We present the foundation underlying \(\mathsf {GRAPE}\), based on simultaneous fixpoint computation. As examples, we demonstrate how \(\mathsf {GRAPE}\) parallelizes our familiar sequential graph algorithms. Furthermore, we show that in addition to its programming simplicity, \(\mathsf {GRAPE}\) achieves performance comparable to the state-of-the-art graph systems.