{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:48:07Z","timestamp":1783036087669,"version":"3.54.6"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T00:00:00Z","timestamp":1632096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            We introduce the\n            <jats:italic>Adaptive Massively Parallel Computation<\/jats:italic>\n            (AMPC) model, which is an extension of the\n            <jats:italic>Massively Parallel Computation<\/jats:italic>\n            (MPC) model. At a high level, the AMPC model strengthens the MPC model by storing all messages sent within a round in a distributed data store. In the following round, all machines are provided with random read access to the data store, subject to the same constraints on the total amount of communication as in the MPC model. Our model is inspired by the previous empirical studies of distributed graph algorithms\u00a0[8, 30] using MapReduce and a distributed hash table service\u00a0[17].\n          <\/jats:p>\n          <jats:p>\n            This extension allows us to give new graph algorithms with much lower round complexities compared to the best-known solutions in the MPC model. In particular, in the AMPC model we show how to solve maximal independent set in\n            <jats:italic>O<\/jats:italic>\n            (1) rounds and connectivity\/minimum spanning tree in\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:sub>\n              <jats:italic>m<\/jats:italic>\n              \/\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            rounds both using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03b4<\/jats:sup>\n            ) space per machine for constant \u03b4 &lt; 1. In the same memory regime for MPC, the best-known algorithms for these problems require poly log\n            <jats:italic>n<\/jats:italic>\n            rounds. Our results imply that the 2-C\n            <jats:sc>YCLE<\/jats:sc>\n            conjecture, which is widely believed to hold in the MPC model, does not hold in the AMPC model.\n          <\/jats:p>","DOI":"10.1145\/3470631","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T18:27:58Z","timestamp":1632162478000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Massively Parallel Computation via Remote Memory Access"],"prefix":"10.1145","volume":"8","author":[{"given":"Soheil","family":"Behnezhad","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hossein","family":"Esfandiari","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"\u0141\u0105cki","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Warren","family":"Schudy","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73035"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_2_1_3_1","unstructured":"Apache Software Foundation. [n.d.]. Beam. Retrieved from https:\/\/beam.apache.org.  Apache Software Foundation. [n.d.]. Beam. Retrieved from https:\/\/beam.apache.org."},{"key":"e_1_2_1_4_1","unstructured":"Apache Software Foundation. [n.d.]. Giraph. Retrieved from https:\/\/giraph.apache.org.  Apache Software Foundation. [n.d.]. Giraph. Retrieved from https:\/\/giraph.apache.org."},{"key":"e_1_2_1_5_1","unstructured":"Apache Software Foundation. [n.d.]. Hadoop. Retrieved from https:\/\/hadoop.apache.org.  Apache Software Foundation. [n.d.]. Hadoop. Retrieved from https:\/\/hadoop.apache.org."},{"key":"e_1_2_1_6_1","unstructured":"InfiniBand Trade Association. [n.d.]. Retrieved from https:\/\/www.infinibandta.org\/.  InfiniBand Trade Association. [n.d.]. Retrieved from https:\/\/www.infinibandta.org\/."},{"key":"e_1_2_1_7_1","volume-title":"Supplement to InfiniBand Architecture Specification","author":"InfiniBand Trade Association","unstructured":"InfiniBand Trade Association . 2010. Supplement to InfiniBand Architecture Specification Volume 1 Release 1.2.2 Annex A16: RDMA over Converged Ethernet (RoCE) . InfiniBand Trade Association. 2010. Supplement to InfiniBand Architecture Specification Volume 1 Release 1.2.2 Annex A16: RDMA over Converged Ethernet (RoCE)."},{"key":"e_1_2_1_8_1","volume-title":"Mirrokni","author":"Bateni MohammadHossein","year":"2017","unstructured":"MohammadHossein Bateni , Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , Raimondas Kiveris , Silvio Lattanzi , and Vahab S . Mirrokni . 2017 . Affinity clustering: Hierarchical clustering at scale. In Advances in Neural Information Processing Systems 30: Proceedings of the Annual Conference on Neural Information Processing Systems, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds .). 6867\u20136877. MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab S. Mirrokni. 2017. Affinity clustering: Hierarchical clustering at scale. In Advances in Neural Information Processing Systems 30: Proceedings of the Annual Conference on Neural Information Processing Systems, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 6867\u20136877."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424579"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00081"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 2015 IEEE 23rd Annual Symposium on High-Performance Interconnects (HOTI\u201915)","author":"Birrittella Mark S.","year":"2015","unstructured":"Mark S. Birrittella , Mark Debbage , Ram Huggahalli , James Kunz , Tom Lovett , Todd Rimmer , Keith D. Underwood , and Robert C. Zak . 2015. Intel\u00aeOmni-path architecture: Enabling scalable, high performance fabrics . In Proceedings of the 2015 IEEE 23rd Annual Symposium on High-Performance Interconnects (HOTI\u201915) . IEEE Computer Society, Los Alamitos, CA, 1\u20139. https:\/\/doi.org\/10.1109\/HOTI. 2015 .22 10.1109\/HOTI.2015.22 Mark S. Birrittella, Mark Debbage, Ram Huggahalli, James Kunz, Tom Lovett, Todd Rimmer, Keith D. Underwood, and Robert C. Zak. 2015. Intel\u00aeOmni-path architecture: Enabling scalable, high performance fabrics. In Proceedings of the 2015 IEEE 23rd Annual Symposium on High-Performance Interconnects (HOTI\u201915). IEEE Computer Society, Los Alamitos, CA, 1\u20139. https:\/\/doi.org\/10.1109\/HOTI.2015.22"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_2_1_15_1","volume-title":"Maggs","author":"Blelloch Guy E.","year":"2010","unstructured":"Guy E. Blelloch and Bruce M . Maggs . 2010 . Parallel Algorithms. In Algorithms and Theory of Computation Handbook. Chapman & Hall\/CRC , 25\u201325. http:\/\/dl.acm.org\/citation.cfm?id=1882723.1882748. Guy E. Blelloch and Bruce M. Maggs. 2010. Parallel Algorithms. In Algorithms and Theory of Computation Handbook. Chapman & Hall\/CRC, 25\u201325. http:\/\/dl.acm.org\/citation.cfm?id=1882723.1882748."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806638"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400230"},{"key":"e_1_2_1_19_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd edition). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition). MIT Press.","edition":"3"},{"key":"e_1_2_1_20_1","unstructured":"Intel Corporation. [n.d.]. Intel Omni-Path Architecture. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/high-per formance-computing-fabrics\/omni-path-driving-exascale-computing.html.  Intel Corporation. [n.d.]. Intel Omni-Path Architecture. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/high-per formance-computing-fabrics\/omni-path-driving-exascale-computing.html."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_22_1","first-page":"3","article-title":"RDMA reads: To use or not to use?IEEE Data","volume":"40","author":"Dragojevic Aleksandar","year":"2017","unstructured":"Aleksandar Dragojevic , Dushyanth Narayanan , and Miguel Castro . 2017 . RDMA reads: To use or not to use?IEEE Data Eng. Bull. 40 , 1 (2017), 3 \u2013 14 . Aleksandar Dragojevic, Dushyanth Narayanan, and Miguel Castro. 2017. RDMA reads: To use or not to use?IEEE Data Eng. Bull. 40, 1 (2017), 3\u201314.","journal-title":"Eng. Bull."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914)","author":"Dragojevi\u0107 Aleksandar","year":"2014","unstructured":"Aleksandar Dragojevi\u0107 , Dushyanth Narayanan , Miguel Castro , and Orion Hodson . 2014 . FaRM: Fast remote memory . In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914) . 401\u2013414. Aleksandar Dragojevi\u0107, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. 2014. FaRM: Fast remote memory. In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914). 401\u2013414."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_2_1_27_1","volume-title":"Algorithm\u00a0447: Efficient algorithms for graph manipulation. Commun. ACM","author":"Hopcroft John","year":"1973","unstructured":"John Hopcroft and Robert Tarjan . 1973. Algorithm\u00a0447: Efficient algorithms for graph manipulation. Commun. ACM ( 1973 ). John Hopcroft and Robert Tarjan. 1973. Algorithm\u00a0447: Efficient algorithms for graph manipulation. Commun. ACM (1973)."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2014 ACM Conference on SIGCOMM (SIGCOMM\u201914)","author":"Kalia Anuj","year":"1923","unstructured":"Anuj Kalia , Michael Kaminsky , and David G. Andersen . 2014. Using RDMA efficiently for key-value services . In Proceedings of the 2014 ACM Conference on SIGCOMM (SIGCOMM\u201914) . ACM, New York, NY, 295\u2013306. https:\/\/doi.org\/10.1145\/26 1923 9.2626299 10.1145\/2619239.2626299 Anuj Kalia, Michael Kaminsky, and David G. Andersen. 2014. Using RDMA efficiently for key-value services. In Proceedings of the 2014 ACM Conference on SIGCOMM (SIGCOMM\u201914). ACM, New York, NY, 295\u2013306. https:\/\/doi.org\/10.1145\/2619239.2626299"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670997"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914)","author":"Lim Hyeontaek","year":"2014","unstructured":"Hyeontaek Lim , Dongsu Han , David G. Andersen , and Michael Kaminsky . 2014 . MICA: A holistic approach to fast in-memory key-value storage . In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914) . USENIX Association, 429\u2013444. https:\/\/www.usenix.org\/conference\/nsdi14\/technical-sessions\/presentation\/lim. Hyeontaek Lim, Dongsu Han, David G. Andersen, and Michael Kaminsky. 2014. MICA: A holistic approach to fast in-memory key-value storage. In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914). USENIX Association, 429\u2013444. https:\/\/www.usenix.org\/conference\/nsdi14\/technical-sessions\/presentation\/lim."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/41287.41291"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2535461.2535475"},{"key":"e_1_2_1_35_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 1995. Randomized Algorithms . Cambridge University Press . Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Huy","year":"2008","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements . In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908) . 327\u2013336. https:\/\/doi.org\/10.1109\/FOCS. 2008 .81 10.1109\/FOCS.2008.81 Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908). 327\u2013336. https:\/\/doi.org\/10.1109\/FOCS.2008.81"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806887"},{"key":"e_1_2_1_38_1","unstructured":"Vijaya Ramachandran. 1993. Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity. In Synthesis of Parallel Algorithms.  Vijaya Ramachandran. 1993. Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity. In Synthesis of Parallel Algorithms."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201916)","author":"Roughgarden Tim","unstructured":"Tim Roughgarden , Sergei Vassilvitskii , and Joshua R. Wang . 2016. Shuffles and Circuits (on lower bounds for modern parallel computation) . In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201916) , Christian Scheideler and Seth Gilbert (Eds.). ACM, 1\u201312. https:\/\/doi.org\/10.1145\/2935764.2935799 10.1145\/2935764.2935799 Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. 2016. Shuffles and Circuits (on lower bounds for modern parallel computation). In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201916), Christian Scheideler and Seth Gilbert (Eds.). ACM, 1\u201312. https:\/\/doi.org\/10.1145\/2935764.2935799"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 1st Workshop on Randomized Parallel Algorithms. 1\u201321","author":"Sanders Peter","unstructured":"Peter Sanders . [n.d.]. On the competitive analysis of randomized static load balancing . In Proceedings of the 1st Workshop on Randomized Parallel Algorithms. 1\u201321 . Peter Sanders. [n.d.]. On the competitive analysis of randomized static load balancing. In Proceedings of the 1st Workshop on Randomized Parallel Algorithms. 1\u201321."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_43_1","volume-title":"Tarjan and Uzi Vishkin","author":"Robert","year":"1985","unstructured":"Robert E. Tarjan and Uzi Vishkin . 1985 . An efficient parallel biconnectivity algorithm. SIAM J. Comput . (1985). Robert E. Tarjan and Uzi Vishkin. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Comput. (1985)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_45_1","volume-title":"[n.d.]. Weak convergence and empirical processes with applications to statistics","author":"van der Vaart Aad W.","unstructured":"Aad W. van der Vaart and Jon A. Wellner . [n.d.]. Weak convergence and empirical processes with applications to statistics . Springer Science & Business Media . Aad W. van der Vaart and Jon A. Wellner. [n.d.]. Weak convergence and empirical processes with applications to statistics. Springer Science & Business Media."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918), Jennifer G. Dy and Andreas Krause (Eds.), JMLR Workshop and Conference Proceedings","volume":"80","author":"Yaroslavtsev Grigory","year":"2018","unstructured":"Grigory Yaroslavtsev and Adithya Vadapalli . 2018 . Massively parallel algorithms and hardness for single-linkage clustering under -distances . In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918), Jennifer G. Dy and Andreas Krause (Eds.), JMLR Workshop and Conference Proceedings , Vol. 80 . 5596\u20135605. Grigory Yaroslavtsev and Adithya Vadapalli. 2018. Massively parallel algorithms and hardness for single-linkage clustering under -distances. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918), Jennifer G. Dy and Andreas Krause (Eds.), JMLR Workshop and Conference Proceedings, Vol. 80. 5596\u20135605."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055335"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470631","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470631"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,20]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3470631"],"URL":"https:\/\/doi.org\/10.1145\/3470631","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,20]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}