{"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":1783576828436,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union's Horizon 2020 Research and Innovation Program","award":["755839"],"award-info":[{"award-number":["755839"]}]},{"name":"Swiss National Foundation","award":["200021_184735"],"award-info":[{"award-number":["200021_184735"]}]},{"name":"Defense Advanced Research Projects Agency (DARPA)","award":["HR00112020023"],"award-info":[{"award-number":["HR00112020023"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467928","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"223-233","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Constant-Round Spanners and Shortest Paths in Congested Clique and MPC"],"prefix":"10.1145","author":[{"given":"Michal","family":"Dory","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Orr","family":"Fischer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seri","family":"Khoury","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dean","family":"Leitersdorf","sequence":"additional","affiliation":[{"name":"Technion, Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129767"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89572"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_2_9_1","volume-title":"Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31 International Symposium on Distributed Computing.","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 31 International Symposium on Distributed Computing. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31 International Symposium on Distributed Computing."},{"key":"e_1_3_2_2_10_1","volume-title":"Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR","author":"Behnezhad Soheil","year":"2018","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , and MohammadTaghi Hajiaghayi . 2018 . Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR , Vol. abs\/ 1802 .10297 (2018). arxiv: 1802.10297 http:\/\/arxiv.org\/abs\/1802.10297 Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. 2018. Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, Vol. abs\/1802.10297 (2018). arxiv: 1802.10297 http:\/\/arxiv.org\/abs\/1802.10297"},{"key":"e_1_3_2_2_11_1","volume-title":"Massively Parallel Algorithms for Distance Approximation and Spanners. SPAA 2021","author":"Biswas Amartya Shankha","year":"2021","unstructured":"Amartya Shankha Biswas , Michal Dory , Mohsen Ghaffari , Slobodan Mitrovic , and Yasamin Nazari . 2021 . Massively Parallel Algorithms for Distance Approximation and Spanners. SPAA 2021 (2021). Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari, Slobodan Mitrovic, and Yasamin Nazari. 2021. Massively Parallel Algorithms for Distance Approximation and Spanners. SPAA 2021 (2021)."},{"key":"e_1_3_2_2_12_1","volume-title":"Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016","author":"Bodwin Greg","year":"2016","unstructured":"Greg Bodwin and Sebastian Krinninger . 2016 . Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016 , August 22-24, 2016, Aarhus, Denmark. 17:1--17:18. Greg Bodwin and Sebastian Krinninger. 2016. Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. 17:1--17:18."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212758"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331633"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0270-2"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_10"},{"key":"e_1_3_2_2_17_1","volume-title":"2019 b. Sparse matrix multiplication and triangle listing in the congested clique model. Theoretical Computer Science","author":"Censor-Hillel Keren","year":"2019","unstructured":"Keren Censor-Hillel , Dean Leitersdorf , and Elia Turner . 2019 b. Sparse matrix multiplication and triangle listing in the congested clique model. Theoretical Computer Science ( 2019 ). Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. 2019 b. Sparse matrix multiplication and triangle listing in the congested clique model. Theoretical Computer Science (2019)."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484268"},{"key":"e_1_3_2_2_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 , Third Edition 3 rd ed.). The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition 3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_3_2_2_20_1","volume-title":"Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI). USENIX Association","author":"Dean Jeffrey","year":"2004","unstructured":"Jeffrey Dean and Sanjay Ghemawat . 2004 . MapReduce: Simplified Data Processing on Large Clusters . In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI). USENIX Association , Berkeley, CA, USA, 10--10. http:\/\/dl.acm.org\/citation.cfm?id=1251254.1251264 Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified Data Processing on Large Clusters. In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI). USENIX Association, Berkeley, CA, USA, 10--10. http:\/\/dl.acm.org\/citation.cfm?id=1251254.1251264"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"key":"e_1_3_2_2_22_1","volume-title":"Distributed Distance-Bounded Network Design Through Distributed Convex Programming. In 21st International Conference on Principles of Distributed Systems, OPODIS","author":"Dinitz Michael","year":"2017","unstructured":"Michael Dinitz and Yasamin Nazari . 2017 . Distributed Distance-Bounded Network Design Through Distributed Convex Programming. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017. 5:1--5:19. Michael Dinitz and Yasamin Nazari. 2017. Distributed Distance-Bounded Network Design Through Distributed Convex Programming. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017. 5:1--5:19."},{"key":"e_1_3_2_2_23_1","volume-title":"Massively Parallel Approximate Distance Sketches. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019","author":"Dinitz Michael","year":"2019","unstructured":"Michael Dinitz and Yasamin Nazari . 2019 . Massively Parallel Approximate Distance Sketches. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019 , December 17-19, 2019, Neuch\u00e2 tel, Switzerland. 35:1--35:17. Michael Dinitz and Yasamin Nazari. 2019. Massively Parallel Approximate Distance Sketches. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17-19, 2019, Neuch\u00e2 tel, Switzerland. 35:1--35:17."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405711"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921666"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331635"},{"key":"e_1_3_2_2_29_1","first-page":"1","article-title":"Efficient algorithms for constructing very sparse spanners and emulators","volume":"15","author":"Elkin Michael","year":"2018","unstructured":"Michael Elkin and Ofer Neiman . 2018 . Efficient algorithms for constructing very sparse spanners and emulators . ACM Transactions on Algorithms (TALG) , Vol. 15 , 1 (2018), 1 -- 29 . Michael Elkin and Ofer Neiman. 2018. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), Vol. 15, 1 (2018), 1--29.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011791"},{"key":"e_1_3_2_2_31_1","volume-title":"Proceedings of Symposium Smolenice. Publ. House Cszechoslovak Acad. Sci., Prague, 29--36","author":"Paul","year":"1964","unstructured":"Paul ErdHo s. 1964 . Extremal problems in graph theory. In Theory Of Graphs And Its Applications , Proceedings of Symposium Smolenice. Publ. House Cszechoslovak Acad. Sci., Prague, 29--36 . Paul ErdHo s. 1964. Extremal problems in graph theory. In Theory Of Graphs And Its Applications, Proceedings of Symposium Smolenice. Publ. House Cszechoslovak Acad. Sci., Prague, 29--36."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.113"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.029"},{"key":"e_1_3_2_2_35_1","volume-title":"Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS","author":"Holzer Stephan","year":"2016","unstructured":"Stephan Holzer and Nathan Pinsker . 2016 . Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Stephan Holzer and Nathan Pinsker. 2016. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331628"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611497"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_2_40_1","volume-title":"Deterministic MST Sparsification in the Congested Clique. CoRR","author":"Korhonen Janne H.","year":"2022","unstructured":"Janne H. Korhonen . 2016. Deterministic MST Sparsification in the Congested Clique. CoRR , Vol. abs\/ 1605 .0 2022 (2016). Janne H. Korhonen. 2016. Deterministic MST Sparsification in the Congested Clique. CoRR, Vol. abs\/1605.02022 (2016)."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_5"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451136"},{"key":"e_1_3_2_2_45_1","volume-title":"Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing, DISC 2018","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 , New Orleans, LA, USA , October 15-19, 2018. 40:1-40:18. Merav Parter and Eylon Yogev. 2018. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018. 40:1-40:18."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_2_48_1","series-title":"SIAM Journal on computing","volume-title":"An optimal synchronizer for the hypercube","author":"Peleg David","year":"1989","unstructured":"David Peleg and Jeffrey D Ullman . 1989. An optimal synchronizer for the hypercube . SIAM Journal on computing , Vol. 18 , 4 ( 1989 ), 740--747. David Peleg and Jeffrey D Ullman. 1989. An optimal synchronizer for the hypercube. SIAM Journal on computing, Vol. 18, 4 (1989), 740--747."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"crossref","unstructured":"Liam Roditty Mikkel Thorup and Uri Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata Languages and Programming (ICALP). 261--272.  Liam Roditty Mikkel Thorup and Uri Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata Languages and Programming (ICALP). 261--272.","DOI":"10.1007\/11523468_22"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_2_53_1","volume-title":"Hadoop: The Definitive Guide","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_2_54_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":"PODC '21: ACM Symposium on Principles of Distributed Computing","location":"Virtual Event Italy","acronym":"PODC '21","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467928","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":54,"alternative-id":["10.1145\/3465084.3467928","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467928","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}