{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T00:05:46Z","timestamp":1755993946518,"version":"3.44.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["14207820, 14203421, and 14222822"],"award-info":[{"award-number":["14207820, 14203421, and 14222822"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>This paper studies communication-oblivious algorithms under the massively parallel computation (MPC) model. The communication patterns of these algorithms follow a distribution dependent only on the definition of the underlying problem, the problem size N, and the number p of machines, but not on the specific input elements. Our objective is to understand when obliviousness necessitates --- or does not necessitate --- heavier communication compared to the traditional MPC model that does not enforce such a requirement.<\/jats:p>\n          <jats:p>The first part of our investigation focuses on single-round algorithms. We prove that skew-free hashing, a fundamental problem solvable with load \u00d5(N\/p) (with high probability or w.h.p.\\ for short) under the traditional model, demands a load of nearly \u03a9(N) under communication obliviousness. Intriguingly, we show that hashing can still be applied in an oblivious manner to process any natural join in one round with a load complexity matching that of the best traditional MPC algorithm. The second part of our investigation studies compilation methods that convert a traditional MPC algorithm A into a communication-oblivious counterpart. Given an A that operates within l = poly(p) rounds and entails a load at most L = \u03a9(p log p) w.h.p., we can produce w.h.p.\\ a communication-oblivious version running in 2l rounds with a load at most (1 + \u03b4) L, where \u03b4 &lt; 0 can be an arbitrarily small constant. Additionally, we establish hardness results indicating that the theoretical guarantees of our compilation can no longer be significantly improved.<\/jats:p>","DOI":"10.1145\/3695832","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-24","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Communication Obliviousness: One Round and Beyond"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1630-9196","authenticated-orcid":false,"given":"Ru","family":"Wang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7883-3458","authenticated-orcid":false,"given":"Shiyuan","family":"Deng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"GYM: A Multiround Distributed Join Algorithm","volume":"4","author":"Afrati Foto N.","year":"2017","unstructured":"Foto N. Afrati, Manas R. Joglekar, Christopher R\u00e9, Semih Salihoglu, and Jeffrey D. Ullman. 2017. GYM: A Multiround Distributed Join Algorithm. In Proceedings of International Conference on Database Theory (ICDT). 4:1--4:18.","journal-title":"Proceedings of International Conference on Database Theory (ICDT)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9627-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488334"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2015836.2015849"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3566049"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319697"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture","volume":"151","author":"Hubert Chan T.-H.","year":"2020","unstructured":"T.-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, and Elaine Shi. 2020. MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. In Innovations in Theoretical Computer Science (ITCS), Vol. 151. 75:1--75:52.","journal-title":"Innovations in Theoretical Computer Science (ITCS)"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461554"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458319"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387657"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3311967"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(2:6)2022"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of International Conference on Database Theory (ICDT). 8:1--8:18","author":"Koutris Paraschos","year":"2016","unstructured":"Paraschos Koutris, Paul Beame, and Dan Suciu. 2016. Worst-Case Optimal Algorithms for Parallel Query Processing. In Proceedings of International Conference on Database Theory (ICDT). 8:1--8:18."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00087"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458321"},{"key":"e_1_2_1_23_1","volume-title":"Ullman","author":"Scheinerman Edward R.","year":"1997","unstructured":"Edward R. Scheinerman and Daniel H. Ullman. 1997. Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Wiley, New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2188349.2188354"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","volume":"98","author":"Tao Yufei","year":"2018","unstructured":"Yufei Tao. 2018. Massively Parallel Entity Matching with Linear Classification in Low Dimensional Space. In Proceedings of International Conference on Database Theory (ICDT), Vol. 98. 20:1--20:19."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:34:35Z","timestamp":1755916475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695832"],"URL":"https:\/\/doi.org\/10.1145\/3695832","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}