{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T04:56:37Z","timestamp":1770612997735,"version":"3.49.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T00:00:00Z","timestamp":1522454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1527867, CCF-1540512, IIS-1633720, and CCF-1717075"],"award-info":[{"award-number":["CCF-1527867, CCF-1540512, IIS-1633720, and CCF-1717075"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"US-Israel Binational Science Foundation","award":["2008348"],"award-info":[{"award-number":["2008348"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where\n            <jats:italic>k<\/jats:italic>\n            \u22652 machines jointly perform computations on graphs with\n            <jats:italic>n<\/jats:italic>\n            nodes (typically,\n            <jats:italic>n<\/jats:italic>\n            &gt;\n            <jats:italic>k<\/jats:italic>\n            ). The input graph is assumed to be initially randomly partitioned among the\n            <jats:italic>k<\/jats:italic>\n            machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation.\n          <\/jats:p>\n          <jats:p>\n            Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in \u00d5(\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) rounds (\u00d5 notation hides a polylog(\n            <jats:italic>n<\/jats:italic>\n            ) factor and an additive polylog(\n            <jats:italic>n<\/jats:italic>\n            ) term). This improves over the best previously known bound of \u00d5(\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            ) [Klauck et al., SODA 2015] and is optimal (up to a polylogarithmic factor) in light of an existing lower bound of \u03a9\n            <jats:sup>\u02dc<\/jats:sup>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. Using the connectivity algorithm as a building block, we then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take \u00d5(\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) rounds and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of \u03a9\n            <jats:sup>\u02dc<\/jats:sup>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.\n          <\/jats:p>","DOI":"10.1145\/3209689","type":"journal-article","created":{"date-parts":[[2018,6,15]],"date-time":"2018-06-15T14:14:38Z","timestamp":1529072078000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Fast Distributed Algorithms for Connectivity and MST in Large Graphs"],"prefix":"10.1145","volume":"5","author":[{"given":"Gopal","family":"Pandurangan","sequence":"first","affiliation":[{"name":"University of Houston, Houston, TX, USA"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London"}]},{"given":"Michele","family":"Scquizzato","sequence":"additional","affiliation":[{"name":"University of Houston"}]}],"member":"320","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095205"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154273.3154317"},{"key":"e_1_2_1_6_1","volume-title":"O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm (about a certain minimal problem). Pr\u00e1ce Mor. Pr\u00edrodoved. Spol. v Brne III 3","author":"Bor\u016fvka Otakar","year":"1926"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/100793104"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26784-5_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611488"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195422"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767405"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722157"},{"key":"e_1_2_1_25_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0225-4"},{"key":"e_1_2_1_30_1","volume-title":"Mining of Massive Datasets","author":"Leskovec Jure"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"key":"e_1_2_1_32_1","volume-title":"Distributed Algorithms","author":"Lynch Nancy A."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993853"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09620-9_2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_6"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935785"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055449"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210409"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 47:1--47:15","author":"Sriram"},{"key":"e_1_2_1_45_1","volume-title":"Fox","author":"Qiu Judy","year":"2014"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634169"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0832"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_51_1","unstructured":"Sergei Vassilvitskii. 2015. Models for Parallel Computation (A Hitchhikers\u2019 Guide to Massively Parallel Universes). Retrieved from http:\/\/grigory.us\/blog\/massively-parallel-universes\/.  Sergei Vassilvitskii. 2015. Models for Parallel Computation (A Hitchhikers\u2019 Guide to Massively Parallel Universes). Retrieved from http:\/\/grigory.us\/blog\/massively-parallel-universes\/."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0218-3"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209689","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209689","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:33Z","timestamp":1750210773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,31]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3209689"],"URL":"https:\/\/doi.org\/10.1145\/3209689","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,31]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}