# To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations

arXiv: https://arxiv.org/abs/2010.16012 · HTML: https://mlsanity.com/paper/2010.16012/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2020.

## Built on by (most cited first, 11 of 11)

- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [SpecExec: Massively Parallel Speculative Decoding for Interactive LLM Inference on Consumer Devices](https://mlsanity.com/paper/2406.02532/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Motif Prediction with Graph Neural Networks](https://mlsanity.com/paper/2106.00761/) (2021)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [Accelerating Backward Aggregation in GCN Training with Execution Path Preparing on GPUs](https://mlsanity.com/paper/2204.02662/) (2022)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)

## Abstract (arXiv)

We reduce the cost of communication and synchronization in graph processing by analyzing the fastest way to process graphs: pushing the updates to a shared state or pulling the updates to a private state.We investigate the applicability of this push-pull dichotomy to various algorithms and its impact on complexity, performance, and the amount of used locks, atomics, and reads/writes. We consider 11 graph algorithms, 3 programming models, 2 graph abstractions, and various families of graphs. The conducted analysis illustrates surprising differences between push and pull variants of different algorithms in performance, speed of convergence, and code complexity; the insights are backed up by performance data from hardware counters.We use these findings to illustrate which variant is faster for each algorithm and to develop generic strategies that enable even higher speedups. Our insights can be used to accelerate graph processing engines or libraries on both massively-parallel shared-memory machines as well as distributed-memory systems.