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.1905499e-05
Overall Rank: 10,929 | 24.05%
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,312	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012650678
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
3,831	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7146681e-05
4,560	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.0788254e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05
5,650	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	5.3887172e-05
7,117	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	4.8205884e-05
8,755	Distributed and Streaming Linear Programming in Low Dimensions	2019	PODS	4.4520434e-05
11,440	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,213	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5533861e-05
4,641	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.0215749e-05
2,856	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0120856e-05
5,905	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2746158e-05
1,312	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012650678
11,440	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1905499e-05
11,634	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.1905499e-05
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
11,776	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1905499e-05