# Communication Steps for Parallel Query Processing

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

## Key facts

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

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

- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Fast attention mechanisms: a tale of parallelism](https://mlsanity.com/paper/2509.09001/) (2025)
- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)
- [Distributed k-Means with Outliers in General Metrics](https://mlsanity.com/paper/2202.08173/) (2022)
- [Massively-Parallel Heat Map Sorting and Applications To Explainable Clustering](https://mlsanity.com/paper/2309.07486/) (2023)
- [Scalable and Distributed Silhouette Approximation](https://mlsanity.com/paper/2607.01993/) (2026)

## Abstract (arXiv)

We consider the problem of computing a relational query q on a large input database of size n, using a large number p of servers. The computation is performed in rounds, and each server can receive only O(n/p1-varepsilon) bits of data, where varepsilon ∈ [0,1] is a parameter that controls replication. We examine how many global communication steps are needed to compute q. We establish both lower and upper bounds, in two settings. For a single round of communication, we give lower bounds in the strongest possible model, where arbitrary bits may be exchanged; we show that any algorithm requires varepsilon ≥ 1-1/τ^*, where τ^* is the fractional vertex cover of the hypergraph of q. We also give an algorithm that matches the lower bound for a specific class of databases. For multiple rounds of communication, we present lower bounds in a model where routing decisions for a tuple are tuple-based. We show that for the class of tree-like queries there exists a tradeoff between the number of rounds and the space exponent varepsilon. The lower bounds for multiple rounds are the first of their kind. Our results also imply that transitive closure cannot be computed in O(1) rounds of communication.