Parallel Communication Obliviousness: One Round and Beyond

Summary: Analyzes communication-oblivious MPC algorithms, emphasizing one-round behavior and obliviousness-based compilation. Skew-free hashing incurs Omega(N) load under obliviousness, yet one-round natural joins reach best MPC loads; a compiler converts an l-round MPC with load L into a 2l-round oblivious version with (1+δ)L load. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1950
Venue: PODS
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,925 | 24.00%
DOI: 10.1145/3695832

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,308	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012661651
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
3,833	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7173578e-05
4,562	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.0846728e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05
5,639	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	5.393897e-05
7,122	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	4.8252188e-05
8,759	Distributed and Streaming Linear Programming in Low Dimensions	2019	PODS	4.456315e-05
11,437	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,215	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5577562e-05
4,689	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	5.9980099e-05
2,849	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0195487e-05
5,902	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2796864e-05
1,308	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012661651
11,437	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1945683e-05
11,630	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.1945683e-05
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
11,768	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1945683e-05