{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T14:59:04Z","timestamp":1784905144370,"version":"3.55.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p>\n            We study fundamental graph problems such as\n            <jats:italic>graph connectivity, minimum spanning forest<\/jats:italic>\n            (MSF), and approximate\n            <jats:italic>maximum (weight) matching<\/jats:italic>\n            in a distributed setting. In particular, we focus on the\n            <jats:italic>Adaptive Massively Parallel Computation<\/jats:italic>\n            (AMPC) model, which is a theoretical model that captures MapReduce-like computation augmented with a distributed hash table.\n          <\/jats:p>\n          <jats:p>\n            We show the first AMPC algorithms for all of the studied problems that run in a constant number of rounds and use only\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03f5<\/jats:sup>\n            ) space per machine, where 0 &lt; \u03f5 &lt; 1. Our results improve both upon the previous results in the AMPC model, as well as the best-known results in the MPC model, which is the theoretical model underpinning many popular distributed computation frameworks, such as MapReduce, Hadoop, Beam, Pregel and Giraph.\n          <\/jats:p>\n          <jats:p>Finally, we provide an empirical comparison of the algorithms in the MPC and AMPC models in a fault-tolerant distributed computation environment. We empirically evaluate our algorithms on a set of large real-world graphs and show that our AMPC algorithms can achieve improvements in both running time and round-complexity over optimized MPC baselines.<\/jats:p>","DOI":"10.14778\/3424573.3424579","type":"journal-article","created":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T01:15:32Z","timestamp":1603847732000},"page":"3588-3602","source":"Crossref","is-referenced-by-count":10,"title":["Parallel graph algorithms in constant adaptive rounds"],"prefix":"10.14778","volume":"13","author":[{"given":"Soheil","family":"Behnezhad","sequence":"first","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hossein","family":"Esfandiari","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"Lacki","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Warren","family":"Schudy","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"accessed","author":"Pricing AWS","year":"2020","unstructured":"AWS Pricing , accessed September 6, 2020 . https:\/\/aws.amazon.com\/emr\/pricing\/. AWS Pricing, accessed September 6, 2020. https:\/\/aws.amazon.com\/emr\/pricing\/."},{"key":"e_1_2_1_2_1","volume-title":"accessed","author":"Pricing Google Cloud","year":"2020","unstructured":"Google Cloud Pricing , accessed September 6, 2020 . https:\/\/cloud.google.com\/compute\/all-pricing. Google Cloud Pricing, accessed September 6, 2020. https:\/\/cloud.google.com\/compute\/all-pricing."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294646"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_2_1_7_1","unstructured":"Apache Software Foundation. Beam. https:\/\/beam.apache.org.  Apache Software Foundation. Beam. https:\/\/beam.apache.org."},{"key":"e_1_2_1_8_1","unstructured":"Apache Software Foundation. Hadoop. https:\/\/hadoop.apache.org.  Apache Software Foundation. Hadoop. https:\/\/hadoop.apache.org."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310533"},{"key":"e_1_2_1_10_1","first-page":"333","volume-title":"International Conference on Machine Learning (ICML)","author":"Assadi S.","year":"2019","unstructured":"S. Assadi , M. Bateni , and V. Mirrokni . Distributed weighted matching via randomized composable coresets . In International Conference on Machine Learning (ICML) , pages 333 -- 343 , 2019 . S. Assadi, M. Bateni, and V. Mirrokni. Distributed weighted matching via randomized composable coresets. In International Conference on Machine Learning (ICML), pages 333--343, 2019."},{"key":"e_1_2_1_11_1","unstructured":"I. T. Association. Infiniband.  I. T. Association. Infiniband."},{"key":"e_1_2_1_12_1","volume-title":"Supplement to InfiniBand Architecture Specification","author":"I. T. Association","year":"2010","unstructured":"I. T. Association . Supplement to InfiniBand Architecture Specification Volume 1 Release 1.2.2 Annex a16: RDMA over Converged Ethernet (RoCE) , 2010 . I. T. Association. Supplement to InfiniBand Architecture Specification Volume 1 Release 1.2.2 Annex a16: RDMA over Converged Ethernet (RoCE), 2010."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_14_1","volume-title":"An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik . An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049 , 2003 . V. Batagelj and M. Zaversnik. An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049, 2003."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3295222.3295430"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087601"},{"key":"e_1_2_1_18_1","volume-title":"Brief announcement: Semi-MapReduce meets congested clique. CoRR, abs\/1802.10297","author":"Behnezhad S.","year":"2018","unstructured":"S. Behnezhad , M. Derakhshan , and M. Hajiaghayi . Brief announcement: Semi-MapReduce meets congested clique. CoRR, abs\/1802.10297 , 2018 . S. Behnezhad, M. Derakhshan, and M. Hajiaghayi. Brief announcement: Semi-MapReduce meets congested clique. CoRR, abs\/1802.10297, 2018."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323208"},{"key":"e_1_2_1_20_1","volume-title":"Parallel graph algorithms in constant adaptive rounds: Theory meets practice. CoRR, abs\/1807.10727","author":"Behnezhad S.","year":"2020","unstructured":"S. Behnezhad , L. Dhulipala , H. Esfandiari , J. \u0141\u0105cki , V. Mirrokni , and W. Schudy . Parallel graph algorithms in constant adaptive rounds: Theory meets practice. CoRR, abs\/1807.10727 , 2020 . S. Behnezhad, L. Dhulipala, H. Esfandiari, J. \u0141\u0105cki, V. Mirrokni, and W. Schudy. Parallel graph algorithms in constant adaptive rounds: Theory meets practice. CoRR, abs\/1807.10727, 2020."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00096"},{"key":"e_1_2_1_23_1","volume-title":"Exponentially faster massively parallel maximal matching. CoRR, abs\/1901.03744","author":"Behnezhad S.","year":"2019","unstructured":"S. Behnezhad , M. Hajiaghayi , and D. G. Harris . Exponentially faster massively parallel maximal matching. CoRR, abs\/1901.03744 , 2019 . S. Behnezhad, M. Hajiaghayi, and D. G. Harris. Exponentially faster massively parallel maximal matching. CoRR, abs\/1901.03744, 2019."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882723.1882748"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1809028.1806638"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400230"},{"key":"e_1_2_1_29_1","unstructured":"I. Corporation. Intel Omni-Path Architecture. https:\/\/www.intel.com\/content\/www\/us\/en\/high-performance-computing-fabrics\/omni-path-driving-exascale-computing.html.  I. Corporation. Intel Omni-Path Architecture. https:\/\/www.intel.com\/content\/www\/us\/en\/high-performance-computing-fabrics\/omni-path-driving-exascale-computing.html."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210414"},{"issue":"1","key":"e_1_2_1_33_1","first-page":"3","article-title":"RDMA reads: To use or not to use?","volume":"40","author":"Dragojevic A.","year":"2017","unstructured":"A. Dragojevic , D. Narayanan , and M. Castro . RDMA reads: To use or not to use? IEEE Data Eng. Bull. , 40 ( 1 ): 3 -- 14 , 2017 . A. Dragojevic, D. Narayanan, and M. Castro. RDMA reads: To use or not to use? IEEE Data Eng. Bull., 40(1):3--14, 2017.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2616448.2616486"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175445"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310534"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/140976649"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/3323234.3323236"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670997"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/3217510"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_48_1","volume-title":"Connected components at scale via local contractions. CoRR, abs\/1807.10727","author":"\u0141\u0105cki J.","year":"2018","unstructured":"J. \u0141\u0105cki , V. S. Mirrokni , and M. Wlodarczyk . Connected components at scale via local contractions. CoRR, abs\/1807.10727 , 2018 . J. \u0141\u0105cki, V. S. Mirrokni, and M. Wlodarczyk. Connected components at scale via local contractions. CoRR, abs\/1807.10727, 2018."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3023549.3023589"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1561\/106.00000003"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2535461.2535475"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_56_1","volume-title":"Equivalence classes and conditional hardness in massively parallel computations. CoRR, abs\/2001.02191","author":"Nanongkai D.","year":"2020","unstructured":"D. Nanongkai and M. Scquizzato . Equivalence classes and conditional hardness in massively parallel computations. CoRR, abs\/2001.02191 , 2020 . D. Nanongkai and M. Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. CoRR, abs\/2001.02191, 2020."},{"key":"e_1_2_1_57_1","volume-title":"Stanford InfoLab","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The PageRank citation ranking: Bringing order to the web. Technical report , Stanford InfoLab , 1999 . L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313446"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935799"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/3086827"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387517"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000056"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795114.1795189"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300082"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3424573.3424579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:18:44Z","timestamp":1672219124000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3424573.3424579"}},"subtitle":["theory meets practice"],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":73,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.14778\/3424573.3424579"],"URL":"https:\/\/doi.org\/10.14778\/3424573.3424579","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}