paper

Pregel: A System for Large-Scale Graph Processing

  • Authors:
Read the paper

đź“ś Abstract

Many practical computing problems concern large graphs, such as modeling web pages and links, social networks, and road maps. These have encouraged the development of numerous specialized graph-processing systems. This paper presents a new framework called Pregel for processing large-scale graphs efficiently. Pregel’s programming model, influenced by Valiant’s Bulk Synchronous Parallel model, is suitable for computations that consist of a sequence of iterations. Computation is vertex-centric, where a sequence of steps is applied to each vertex and messages can be sent to other vertices along outgoing edges. We discuss the architecture of Pregel, which is designed to execute on clusters of thousands of commodity computers, and we explain how faulttolerance, message passing, and other features are incorporated into the framework. Experiments on several algorithms demonstrate Pregel’s scalability and performance.

✨ Summary

Pregel is a system developed by Google for processing large-scale graphs efficiently, inspired by Valiant’s Bulk Synchronous Parallel (BSP) model. It introduces a vertex-centric computation model that supports parallel execution on distributed systems. The paper outlines the architecture of Pregel, which is designed to run on clusters of thousands of commodity machines, highlighting its ability to manage fault tolerance and message passing. Pregel’s significance lies in its application to real-world problems such as web graphs, social networks, and network routing.

In terms of impact, Pregel has influenced various subsequent graph processing frameworks and research, including Apache Giraph, an open-source implementation inspired by Pregel’s design. Pregel’s conceptual framework has also led to research into the optimization of graph processing systems for better scalability and efficiency. Notable works that have cited and built upon Pregel include:

  1. “Apache Giraph: current state and review of graph processing” ACM DL
  2. “GraphX: Unifying Data-Parallel and Graph-Parallel Analytics” USENIX
  3. “A Survey of Graph Processing on Clusters” IEEE Xplore
  4. “PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs” OSDI
  5. “GEMS: A graph engine for multi-threaded systems” ACM DL

Pregel remains an important foundation for both academic research and practical applications in large-scale graph processing.