2026-09-26T20:39:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25622 2026-09-23T23:45:07Z ddc:004 open_access

Neither Cover nor Pack: Distributed Worst-Case Optimality of Degree-2 Joins Aamer, Heba Hu, Xiao Ketsman, Bas degree-two joins worst-case optimality distributed algorithms We study the worst-case communication complexity of the join query evaluation problem over large-scale data in distributed shared-nothing systems under the MPC model. We focus on multi-round MPC algorithms that run in constant number of rounds. The problem is well-understood for a few classes of queries, mainly the class of acyclic queries and the class of graph-like queries. For queries not belonging to either class, the complexity picture is much less clear. We study the class of degree-two queries and fragments thereof. In this paper, we tighten the gap between the upper and lower bounds for the studied classes and establish worst-case optimality for some fragments of the considered classes. We also debunk a well-believed conjecture about which query-related quantity, in the worst-case, optimally captures the communication complexity of the studied problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Heba Aamer and Xiao Hu and Bas Ketsman 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.8 urn:nbn:de:0030-drops-256226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode