Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy

Abstract

Processing massive graphs with billions of nodes and edges is a cornerstone of modern data analysis. However, standard distributed models like Massively Parallel Computation (MPC) face a fundamental theoretical bottleneck: many graph problems require $\Omega(\log n)$ communication rounds. This paper introduces a suite of constant-round algorithms for connectivity, minimum spanning forest (MSF), and matching by leveraging the Adaptive Massively Parallel Computation (AMPC) model. By utilizing a distributed hash table (DHT) for random read-access, the proposed algorithms break the logarithmic barrier. Experimental results on massive real-world datasets, including the 225-billion-edge Hyperlink2012 graph, show speedups of up to 7x over optimized MPC baselines.

Introduction: Breaking the Logarithmic Barrier

In large-scale graph processing, communication is the primary bottleneck. Distributed frameworks like MapReduce or Spark are often modeled as MPC, where computation proceeds in synchronous rounds of local processing followed by a global data shuffle. A long-standing challenge in this model is the "1-vs-2-Cycle conjecture," which implies that even simple tasks like graph connectivity require a number of rounds proportional to the diameter of the graph, typically $O(\log n)$.

In practice, each round involves a "shuffle" (moving data across the network), which is incredibly expensive. The authors address this by adopting the Adaptive Massively Parallel Computation (AMPC) model. AMPC extends MPC by allowing machines to perform adaptive queries to a distributed hash table (DHT) containing messages from the previous round. This capability allows for "local exploration" of graph neighborhoods within a single round, potentially reducing the total number of expensive global shuffles to a constant.

Theoretical Contributions and Implementation Scope

The paper provides new $O(1)$ round algorithms for several fundamental problems. The table below summarizes the theoretical bounds achieved in this work compared to previous AMPC results and standard MPC.

Comparison of round complexity bounds and implementation status across AMPC and MPC models.

As shown in the table, the authors achieved constant round complexity for Connectivity and MST, and significantly improved bounds for Matching. Crucially, several of these algorithms were implemented and tested in a production-scale environment, proving that the theoretical $O(1)$ round complexity is achievable in practice.

Algorithmic Methods

The core of the proposed approach involves several innovative techniques designed to exploit the DHT access of the AMPC model:

  1. Ternarization: To handle high-degree vertices without overwhelming individual machines, the authors "ternarize" the graph by replacing high-degree nodes with cycles of degree-3 nodes. This transformation preserves connectivity and MSF properties while enabling work-efficient local exploration.
  2. Truncated Prim’s Algorithm: For MSF, the authors run a modified Prim’s algorithm from every vertex. The search is truncated if it exceeds a certain size or encounters a node with higher random priority. This "shrinking" step reduces the graph size drastically in a single round.
  3. Recursive Matching: The matching algorithm uses recursive sampling to exponentially reduce the maximum degree of the graph in each iteration, eventually solving the problem on a small residual graph.
  4. System Optimization: The implementation uses Flume-C++ and a custom DHT optimized for RDMA (Remote Direct Memory Access). This hardware-level optimization minimizes the latency of DHT lookups, which is critical for the AMPC model's performance.

Experimental Evaluation

The algorithms were evaluated on massive real-world graphs, including Twitter (TW) (2.4B edges), ClueWeb (CW) (74B edges), and Hyperlink2012 (HL) (225B edges).

Key Results

  • Round Reduction: The theoretical $O(1)$ complexity translated directly to practice. For the Hyperlink2012 graph, the AMPC Maximal Independent Set (MIS) algorithm required only 1 shuffle, whereas the MPC version required 14.
  • Performance Gains: The AMPC implementations achieved speedups between 2.3x and 7.2x over highly optimized MPC baselines across different problems and datasets.
  • The Importance of Caching: Client-side caching of DHT queries was found to be essential. Without it, "hot" vertices would bottleneck the DHT, preventing the algorithms from scaling to the largest datasets.
  • RDMA Impact: Using RDMA for DHT lookups provided a 1.5x to 6x speedup over traditional TCP/IP, highlighting the importance of hardware-level optimizations for modern distributed algorithms.

Conclusion and Future Directions

This work demonstrates that the AMPC model is not just a theoretical curiosity but a practical framework for building high-performance distributed graph algorithms. By trading global shuffles for fine-grained DHT queries, the authors successfully broke the logarithmic round barrier for several fundamental problems.

Future work remains in reducing the total query complexity to strictly linear $O(m)$ for all problems and exploring the applicability of AMPC to more complex graph analytics like community detection or graph embeddings. Additionally, addressing network saturation during heavy query phases will be vital for further scaling on even larger clusters.

Summary updated

BibTeX
@article{behnezhad2020parallel,
  author = {Soheil Behnezhad and Laxman Dhulipala and Hossein Esfandiari and Jakub Lacki and Vahab S. Mirrokni and Warren Schudy},
  title = {{Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice}},
  journal = {Proc. VLDB Endow.},
  year = {2020},
  doi = {10.14778/3424573.3424579},
}
Figure