{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:00:28Z","timestamp":1783576828447,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["No. 853109"],"award-info":[{"award-number":["No. 853109"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss NSF","award":["P400P2\\_191122\/1"],"award-info":[{"award-number":["P400P2\\_191122\/1"]}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1733808, IIS-1741137, CCF-190911"],"award-info":[{"award-number":["CCF-1733808, IIS-1741137, CCF-190911"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fintech@CSAIL"},{"name":"MIT-IBM Watson AI Lab and Research Collaboration","award":["W1771646"],"award-info":[{"award-number":["W1771646"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,6]]},"DOI":"10.1145\/3409964.3461784","type":"proceedings-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T23:07:02Z","timestamp":1625094422000},"page":"118-128","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Massively Parallel Algorithms for Distance Approximation and Spanners"],"prefix":"10.1145","author":[{"given":"Amartya Shankha","family":"Biswas","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Dory","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Slobodan","family":"Mitrovi\u0107","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yasamin","family":"Nazari","sequence":"additional","affiliation":[{"name":"Johns Hopkins University, Baltimore, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Kook Jin Ahn and Sudipto Guha. 2015. Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching Under Resource Constraints. In SPAA. 202--211.  Kook Jin Ahn and Sudipto Guha. 2015. Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching Under Resource Constraints. In SPAA. 202--211."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 459--467","author":"Ahn K. J.","unstructured":"K. J. Ahn , S. Guha , and A. McGregor . 2012. Analyzing graph structure via linear measurements . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 459--467 . K. J. Ahn, S. Guha, and A. McGregor. 2012. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 459--467."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_5_1","volume-title":"Proc. ICALP, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.)","volume":"132","author":"Andoni Alexandr","year":"2019","unstructured":"Alexandr Andoni , Clifford Stein , and Peilin Zhong . 2019 . Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity . In Proc. ICALP, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) , Vol. 132 . 14:1--14:16. Alexandr Andoni, Clifford Stein, and Peilin Zhong. 2019. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In Proc. ICALP, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.), Vol. 132. 14:1--14:16."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384321"},{"key":"e_1_3_2_1_7_1","volume-title":"Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi . 2017. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 ( 2017 ). Sepehr Assadi. 2017. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 (2017)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.98"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. Symposium on DIStributed Computing (DISC)","volume":"91","author":"Becker Ruben","year":"2017","unstructured":"Ruben Becker , Andreas Karrenbauer , Sebastian Krinninger , and Christoph Lenzen . 2017 . Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models . In Proc. Symposium on DIStributed Computing (DISC) , Vol. 91 . 7:1--7:16. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In Proc. Symposium on DIStributed Computing (DISC), Vol. 91. 7:1--7:16."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_1_16_1","volume-title":"Mirrokni","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad , Laxman Dhulipala , Hossein Esfandiari , Jakub Lacki , and Vahab S . Mirrokni . 2019 . Near-Optimal Massively Parallel Graph Connectivity. In Proc. Foundations of Computer Science (FOCS), David Zuckerman (Ed .). 1615--1636. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. In Proc. Foundations of Computer Science (FOCS), David Zuckerman (Ed.). 1615--1636."},{"key":"e_1_3_2_1_17_1","volume-title":"Harris","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad , MohammadTaghi Hajiaghayi , and David G . Harris . 2019 . Exponentially Faster Massively Parallel Maximal Matching. In Proc. Foundations of Computer Science (FOCS), David Zuckerman (Ed .). 1637--1649. Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching. In Proc. Foundations of Computer Science (FOCS), David Zuckerman (Ed.). 1637--1649."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.104"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175346"},{"key":"e_1_3_2_1_20_1","volume-title":"Breaking the LinearMemory Barrier in MPC: Fast MIS on Trees with Memory per Machine. arXiv preprint arXiv:1802.06748","author":"Brandt Sebastian","year":"2018","unstructured":"Sebastian Brandt , Manuela Fischer , and Jara Uitto . 2018. Breaking the LinearMemory Barrier in MPC: Fast MIS on Trees with Memory per Machine. arXiv preprint arXiv:1802.06748 ( 2018 ). Sebastian Brandt, Manuela Fischer, and Jara Uitto. 2018. Breaking the LinearMemory Barrier in MPC: Fast MIS on Trees with Memory per Machine. arXiv preprint arXiv:1802.06748 (2018)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of International Conference on Principles of Distributed Systems (OPODIS","author":"Dinitz Michael","year":"2019","unstructured":"Michael Dinitz and Yasamin Nazari . 2019 . Massively Parallel Approximate Distance Sketches . In Proceedings of International Conference on Principles of Distributed Systems (OPODIS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Michael Dinitz and Yasamin Nazari. 2019. Massively Parallel Approximate Distance Sketches. In Proceedings of International Conference on Principles of Distributed Systems (OPODIS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.113"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231591"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_2_1_30_1","unstructured":"Mohsen Ghaffari Themis Gouleakis Christian Konrad Slobodan Mitrovi\u0107 and Ronitt Rubinfeld. [n.d.]. Improved massively parallel computation algorithms for mis matching and vertex cover. In PODC vfill .  Mohsen Ghaffari Themis Gouleakis Christian Konrad Slobodan Mitrovi\u0107 and Ronitt Rubinfeld. [n.d.]. Improved massively parallel computation algorithms for mis matching and vertex cover. In PODC vfill ."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.)","volume":"97","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari , Silvio Lattanzi , and Slobodan Mitrovic . 2019 . Improved Parallel Algorithms for Density-Based Network Clustering . In Proceedings of the International Conference on Machine Learning (ICML), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) , Vol. 97 . PMLR, 2201--2210. Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In Proceedings of the International Conference on Machine Learning (ICML), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 2201--2210."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405737"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_1_36_1","volume-title":"Proc","author":"Goodrich Michael T.","unstructured":"Michael T. Goodrich , Nodari Sitchinava , and Qin Zhang . 2011. Sorting , searching, and simulation in the MapReduce framework . In Proc . ISAAC. Springer , 374--383. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, searching, and simulation in the MapReduce framework. In Proc. ISAAC. Springer, 374--383."},{"key":"e_1_3_2_1_37_1","volume-title":"MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond. arXiv preprint arXiv:1905.01748","author":"Hajiaghayi MohammadTaghi","year":"2019","unstructured":"MohammadTaghi Hajiaghayi , Silvio Lattanzi , Saeed Seddighin , and Cliff Stein . 2019. MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond. arXiv preprint arXiv:1905.01748 ( 2019 ). MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin, and Cliff Stein. 2019. MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond. arXiv preprint arXiv:1905.01748 (2019)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.029"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Giuseppe F. Italiano Silvio Lattanzi Vahab S. Mirrokni and Nikos Parotsidis. 2019. Dynamic Algorithms for the Massively Parallel Computation Model. In SPAA. 49--58.  Giuseppe F. Italiano Silvio Lattanzi Vahab S. Mirrokni and Nikos Parotsidis. 2019. Dynamic Algorithms for the Massively Parallel Computation Model. In SPAA. 49--58.","DOI":"10.1145\/3323165.3323202"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611497"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_45_1","volume-title":"Proc. Symposium on Theory of Computation (STOC).","author":"Lacki Jakub","year":"2020","unstructured":"Jakub Lacki , Slobodan Mitrovic , Krzysztof Onak , and Piotr Sankowski . 2020 . Walking Randomly, Massively, and Efficiently . In Proc. Symposium on Theory of Computation (STOC). Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. 2020. Walking Randomly, Massively, and Efficiently. In Proc. Symposium on Theory of Computation (STOC)."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Silvio Lattanzi Benjamin Moseley Siddharth Suri and Sergei Vassilvitskii. 2011. Filtering: a method for solving graph problems in MapReduce. In SPAA. 85--94.  Silvio Lattanzi Benjamin Moseley Siddharth Suri and Sergei Vassilvitskii. 2011. Filtering: a method for solving graph problems in MapReduce. In SPAA. 85--94.","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384268"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_49_1","volume-title":"Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing (DISC","author":"Parter Merav","year":"2018","unstructured":"Merav Parter and Eylon Yogev . 2018 . Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Merav Parter and Eylon Yogev. 2018. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_1_52_1","volume-title":"Wang","author":"Roughgarden Tim","year":"2016","unstructured":"Tim Roughgarden , Sergei Vassilvitskii , and Joshua R . Wang . 2016 . Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation). In SPAA. 1--12. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. 2016. Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation). In SPAA. 1--12."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_54_1","volume-title":"Hadoop: The definitive guide. \" O'Reilly Media","author":"White Tom","year":"2012","unstructured":"Tom White . 2012 . Hadoop: The definitive guide. \" O'Reilly Media , Inc .\". Tom White. 2012. Hadoop: The definitive guide. \" O'Reilly Media, Inc.\"."},{"key":"e_1_3_2_1_55_1","volume-title":"Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud). https:\/\/www.usenix. org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud). https:\/\/www.usenix. org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud). https:\/\/www.usenix. org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets"}],"event":{"name":"SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461784","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3409964.3461784","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461784","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:08Z","timestamp":1750191428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":55,"alternative-id":["10.1145\/3409964.3461784","10.1145\/3409964"],"URL":"https:\/\/doi.org\/10.1145\/3409964.3461784","relation":{},"subject":[],"published":{"date-parts":[[2021,7,6]]},"assertion":[{"value":"2021-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}