{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:06Z","timestamp":1750220466502,"version":"3.41.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"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, CCF-1717075"],"award-info":[{"award-number":["CCF-1527867, CCF-1540512, IIS-1633720, CCF-1717075"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k \u2265 2 machines jointly perform computations on graphs with\n            <jats:italic>n<\/jats:italic>\n            nodes (typically, n &gt;&gt; k). 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\n            <jats:italic>rounds<\/jats:italic>\n            of the computation.\n          <\/jats:p>\n          <jats:p>\n            Our main contribution is the\n            <jats:italic>General Lower Bound Theorem<\/jats:italic>\n            , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a \u201ccookbook\u201d fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely,\n            <jats:italic>PageRank computation<\/jats:italic>\n            and\n            <jats:italic>triangle enumeration<\/jats:italic>\n            . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input.\n          <\/jats:p>\n          <jats:p>\n            We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in\n            <jats:italic>k<\/jats:italic>\n            , improving significantly over previous results [Klauck et\u00a0al., SODA 2015]. Specifically, we show the following results:\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>PageRank:<\/jats:italic>\n            We show a lower bound of \u1ffa(n\/k\n            <jats:sup>2<\/jats:sup>\n            ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in \u00d5(n\/k\n            <jats:sup>2<\/jats:sup>\n            ) rounds.\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>Triangle enumeration:<\/jats:italic>\n            We show that there exist graphs with\n            <jats:italic>m<\/jats:italic>\n            edges where any distributed algorithm requires \u1ffa(m\/k\n            <jats:sup>5\/3<\/jats:sup>\n            ) rounds. This result also implies the first non-trivial lower bound of \u1ffa(n\n            <jats:sup>1\/3<\/jats:sup>\n            ) rounds for the\n            <jats:italic>congested clique<\/jats:italic>\n            model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in \u00d5(m\/k\n            <jats:sup>5\/3<\/jats:sup>\n            + n\/k\n            <jats:sup>4\/3<\/jats:sup>\n            ) rounds.\n          <\/jats:p>","DOI":"10.1145\/3460900","type":"journal-article","created":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T10:07:31Z","timestamp":1626343651000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Distributed Complexity of Large-Scale Graph Computations"],"prefix":"10.1145","volume":"8","author":[{"given":"Gopal","family":"Pandurangan","sequence":"first","affiliation":[{"name":"University of Houston, Cullen Blvd, Houston, TX, USA"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Kowloon, Hong Kong"}]},{"given":"Michele","family":"Scquizzato","sequence":"additional","affiliation":[{"name":"University of Padova, Padova, Italy"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Giraph http:\/\/giraph.apache.org\/.  Giraph http:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.47"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"volume-title":"Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN\u201918)","author":"Bandyapadhyay Sayan","key":"e_1_2_1_6_1","unstructured":"Sayan Bandyapadhyay , Tanmay Inamdar , Shreyas Pai , and Sriram V. Pemmaraju . 2018. Near-optimal clustering in the -machine model . In Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN\u201918) . 15:1\u201315:10. Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Sriram V. Pemmaraju. 2018. Near-optimal clustering in the -machine model. In Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN\u201918). 15:1\u201315:10."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129098"},{"key":"e_1_2_1_9_1","volume-title":"Wilson","author":"Berry Jonathan W.","year":"2015","unstructured":"Jonathan W. Berry , Luke A. Fostvedt , Daniel J. Nordman , Cynthia A. Phillips , C. Seshadhri , and Alyson G . Wilson . 2015 . Why do simple algorithms for triangle enumeration work in the real world?Internet Math . 11, 6 (2015), 555\u2013571. Jonathan W. Berry, Luke A. Fostvedt, Daniel J. Nordman, Cynthia A. Phillips, C. Seshadhri, and Alyson G. Wilson. 2015. Why do simple algorithms for triangle enumeration work in the real world?Internet Math. 11, 6 (2015), 555\u2013571."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26784-5_14"},{"key":"e_1_2_1_16_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A . Thomas . 2006 . Elements of Information Theory. Wiley-Interscience . Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory. Wiley-Interscience."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.04.003"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611488"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 28th International Conference on Human Factors in Computing Systems. 4027\u20134032","author":"Welles Brooke Foucault","year":"2010","unstructured":"Brooke Foucault Welles , Anne Van Devender , and Noshir Contractor . 2010 . Is a friend a friend?: Investigating the structure of friendship networks in virtual worlds . In Proceedings of the 28th International Conference on Human Factors in Computing Systems. 4027\u20134032 . Brooke Foucault Welles, Anne Van Devender, and Noshir Contractor. 2010. Is a friend a friend?: Investigating the structure of friendship networks in virtual worlds. In Proceedings of the 28th International Conference on Human Factors in Computing Systems. 4027\u20134032."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/248210.248223"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_2_1_26_1","volume-title":"How fast can you update your MST? (Dynamic algorithms for cluster computing). CoRR abs\/2002.06762","author":"Gilbert Seth","year":"2020","unstructured":"Seth Gilbert and Lawrence Li. 2020. How fast can you update your MST? (Dynamic algorithms for cluster computing). CoRR abs\/2002.06762 ( 2020 ). Seth Gilbert and Lawrence Li. 2020. How fast can you update your MST? (Dynamic algorithms for cluster computing). CoRR abs\/2002.06762 (2020)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035920"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"volume-title":"Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS\u201918)","author":"Inamdar Tanmay","key":"e_1_2_1_29_1","unstructured":"Tanmay Inamdar , Shreyas Pai , and Sriram V. Pemmaraju . 2018. Large-scale distributed algorithms for facility location with outliers . In Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS\u201918) . 5:1\u20135:16. Tanmay Inamdar, Shreyas Pai, and Sriram V. Pemmaraju. 2018. Large-scale distributed algorithms for facility location with outliers. In Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS\u201918). 5:1\u20135:16."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087811"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1072830.1072836"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.167"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.28"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing (DISC\u201919)","author":"Konrad Christian","year":"2019","unstructured":"Christian Konrad , Sriram Pemmaraju , Talal Riaz , and Peter Robinson . 2019 . The complexity of symmetry breaking in massive graphs . In Proceedings of the 33rd International Symposium on Distributed Computing (DISC\u201919) . 26:1\u201326:18. Christian Konrad, Sriram Pemmaraju, Talal Riaz, and Peter Robinson. 2019. The complexity of symmetry breaking in massive graphs. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC\u201919). 26:1\u201326:18."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 19th International Conference on Database Theory (ICDT\u201916)","author":"Koutris Paraschos","year":"2016","unstructured":"Paraschos Koutris , Paul Beame , and Dan Suciu . 2016 . Worst-case optimal algorithms for parallel query processing . In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916) . 8:1\u20138:18. Paraschos Koutris, Paul Beame, and Dan Suciu. 2016. Worst-case optimal algorithms for parallel query processing. In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916). 8:1\u20138:18."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384303"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129091"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993639"},{"volume-title":"Mining of Massive Datasets","author":"Leskovec Jure","key":"e_1_2_1_42_1","unstructured":"Jure Leskovec , Anand Rajaraman , and Jeffrey David Ullman . 2014. Mining of Massive Datasets . Cambridge University Press . Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. 2014. Mining of Massive Datasets. Cambridge University Press."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"volume-title":"Distributed Algorithms","author":"Lynch Nancy A.","key":"e_1_2_1_44_1","unstructured":"Nancy A. Lynch . 1996. Distributed Algorithms . Morgan Kaufmann Publishers Inc . Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993853"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS\u201919)","author":"Nanongkai Danupon","year":"2019","unstructured":"Danupon Nanongkai and Michele Scquizzato . 2019 . Equivalence classes and conditional hardness in massively parallel computations . In Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS\u201919) . 33:1\u201333:16. Danupon Nanongkai and Michele Scquizzato. 2019. Equivalence classes and conditional hardness in massively parallel computations. In Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS\u201919). 33:1\u201333:16."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09620-9_2"},{"key":"e_1_2_1_51_1","unstructured":"L. Page S. Brin R. Motwani and T. Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.  L. Page S. Brin R. Motwani and T. Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_6"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.11.017"},{"key":"e_1_2_1_54_1","volume-title":"Tight bounds for distributed graph computations. CoRR abs\/1602.08481","author":"Pandurangan Gopal","year":"2016","unstructured":"Gopal Pandurangan , Peter Robinson , and Michele Scquizzato . 2016. Tight bounds for distributed graph computations. CoRR abs\/1602.08481 ( 2016 ). Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2016. Tight bounds for distributed graph computations. CoRR abs\/1602.08481 (2016)."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209689"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210409"},{"volume-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201916)","author":"Park Ha-Myung","key":"e_1_2_1_57_1","unstructured":"Ha-Myung Park , Sung-Hyon Myaeng , and U. Kang . 2016. PTE: Enumerating trillion triangles on distributed systems . In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201916) . 1115\u20131124. Ha-Myung Park, Sung-Hyon Myaeng, and U. Kang. 2016. PTE: Enumerating trillion triangles on distributed systems. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201916). 1115\u20131124."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699414"},{"volume-title":"An Introduction to Information Theory","author":"Reza Fazlollah M.","key":"e_1_2_1_61_1","unstructured":"Fazlollah M. Reza . 1961. An Introduction to Information Theory . Courier Corporation . Fazlollah M. Reza. 1961. An Introduction to Information Theory. Courier Corporation."},{"key":"e_1_2_1_62_1","volume-title":"Counting cycles and finite dimensional norms. arXiv:math\/0111106","author":"Rivin Igor","year":"2001","unstructured":"Igor Rivin . 2001. Counting cycles and finite dimensional norms. arXiv:math\/0111106 ( 2001 ). Igor Rivin. 2001. Counting cycles and finite dimensional norms. arXiv:math\/0111106 (2001)."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050202"},{"key":"e_1_2_1_64_1","unstructured":"Andrzej Ruci\u0144ski. 2017. Personal communication.  Andrzej Ruci\u0144ski. 2017. Personal communication."},{"key":"e_1_2_1_65_1","series-title":"Lecture Notes in Computer Science","volume-title":"Universal Routing Strategies for Interconnection Networks","author":"Scheideler Christian","unstructured":"Christian Scheideler . 1998. Universal Routing Strategies for Interconnection Networks . Lecture Notes in Computer Science , Vol. 1390 . Springer . Christian Scheideler. 1998. Universal Routing Strategies for Interconnection Networks. Lecture Notes in Computer Science, Vol. 1390. Springer."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_68_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_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","unstructured":"S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.  S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_72_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\/3460900","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460900","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:21Z","timestamp":1750193301000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":72,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3460900"],"URL":"https:\/\/doi.org\/10.1145\/3460900","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}