Pregel: a system for large-scale graph processing. Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs - in some cases billions of vertices, trillions of edges - poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 12 articles )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Ahmed, Aly; Thomo, Alex: Computing source-to-target shortest paths for complex networks in RDBMS (2017)
  2. Lluch Lafuente, Alberto; Loreti, Michele; Montanari, Ugo: Asynchronous distributed execution of fixpoint-based computational fields (2017)
  3. Sonobe, Tomohiro: An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC (2016)
  4. Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.: An exact combinatorial algorithm for minimum graph bisection (2015)
  5. Hegeman, James W.; Pemmaraju, Sriram V.: Sub-logarithmic distributed algorithms for metric facility location (2015)
  6. Younes, Ahmed: A bounded-error quantum polynomial-time algorithm for two graph bisection problems (2015)
  7. Cruz, Flavio; Rocha, Ricardo; Goldstein, Seth Copen; Pfenning, Frank: A linear logic programming language for concurrent programming over graph structures (2014)
  8. Ma, Shuai; Cao, Yang; Fan, Wenfei; Huai, Jinpeng; Wo, Tianyu: Strong simulation: capturing topology in graph pattern matching (2014)
  9. Riedy, E.Jason; Meyerhenke, Henning; Ediger, David; Bader, David A.: Parallel community detection for massive graphs (2013)
  10. Georgiou, Chryssis; Kowalski, Dariusz R.: Performing dynamically injected tasks on processes prone to crashes and restarts (2011)
  11. Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan: Distributed optimization and statistical learning via the alternating direction method of multipliers (2010)
  12. Malewicz, Grzegorz; Austern, Matthew H.; Bik, Aart J.C.; Dehnert, James C.; Horn, Ilan; Leiser, Naty; Czajkowski, Grzegorz: Pregel, a system for large-scale graph processing (abstract) (2009) ioport