{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:55:47Z","timestamp":1750308947889,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T00:00:00Z","timestamp":1506729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MIUR of Italy","award":["AMANDA"],"award-info":[{"award-number":["AMANDA"]}]},{"name":"ERC","award":["614331"],"award-info":[{"award-number":["614331"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1527867, IIS-1633720"],"award-info":[{"award-number":["CCF-1527867, IIS-1633720"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003500","name":"University of Padova","doi-asserted-by":"crossref","award":["STPD08JA32, CPDA121378\/12, CPDA152255\/15"],"award-info":[{"award-number":["STPD08JA32, CPDA121378\/12, CPDA152255\/15"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>Communication is a major factor determining the performance of algorithms on current computing systems; it is therefore valuable to provide tight lower bounds on the communication complexity of computations. This article presents a lower bound technique for the communication complexity in the bulk-synchronous parallel (BSP) model of a given class of DAG computations. The derived bound is expressed in terms of the switching potential of a DAG, that is, the number of permutations that the DAG can realize when viewed as a switching network. The proposed technique yields tight lower bounds for the fast Fourier transform (FFT), and for any sorting and permutation network. A stronger bound is also derived for the periodic balanced sorting network, by applying this technique to suitable subnetworks. Finally, we demonstrate that the switching potential captures communication requirements even in computational models different from BSP, such as the I\/O model and the LPRAM.<\/jats:p>","DOI":"10.1145\/3181776","type":"journal-article","created":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T16:45:32Z","timestamp":1519145132000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Lower Bound Technique for Communication in BSP"],"prefix":"10.1145","volume":"4","author":[{"given":"Gianfranco","family":"Bilardi","sequence":"first","affiliation":[{"name":"University of Padova, Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Scquizzato","sequence":"additional","affiliation":[{"name":"University of Padova"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Silvestri","sequence":"additional","affiliation":[{"name":"University of Padova, Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90188-N"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3018058.3018063"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395121"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00020-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1964.tb04102.x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.35835"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 17th Computing: The Australasian Theory Symposium (CATS\u201911)","author":"Bilardi Gianfranco","year":"2011","unstructured":"Gianfranco Bilardi and Carlo Fantozzi . 2011 . New area-time lower bounds for the multidimensional DFT . In Proceedings of the 17th Computing: The Australasian Theory Symposium (CATS\u201911) . 111--120. Gianfranco Bilardi and Carlo Fantozzi. 2011. New area-time lower bounds for the multidimensional DFT. In Proceedings of the 17th Computing: The Australasian Theory Symposium (CATS\u201911). 111--120."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647681.732330"},{"volume-title":"Handbook of Parallel Computing: Models, Algorithms and Applications","author":"Bilardi Gianfranco","key":"e_1_2_1_14_1","unstructured":"Gianfranco Bilardi , Andrea Pietracaprina , and Geppino Pucci . 2007. Decomposable BSP: A bandwidth-latency model for parallel and hierarchical computation . In Handbook of Parallel Computing: Models, Algorithms and Applications . CRC Press , 277--315. Gianfranco Bilardi, Andrea Pietracaprina, and Geppino Pucci. 2007. Decomposable BSP: A bandwidth-latency model for parallel and hierarchical computation. In Handbook of Parallel Computing: Models, Algorithms and Applications. CRC Press, 277--315."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2812804"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840437"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000131"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32820-6_67"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch , Jeremy T. Fineman , Phillip B. Gibbons , Yan Gu , and Julian Shun . 2016 . Efficient algorithms with asymmetric read and write costs . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . 14:1--14:18. Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. 2016. Efficient algorithms with asymmetric read and write costs. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). 14:1--14:18."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.04.008"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.28"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3040221"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/240455.240477"},{"volume-title":"Proceedings of the 2nd International Conference on Parallel Processing (Euro-Par\u201996)","author":"de la Torre Pilar","key":"e_1_2_1_25_1","unstructured":"Pilar de la Torre and Clyde P. Kruskal . 1996. Submachine locality in the bulk synchronous setting . In Proceedings of the 2nd International Conference on Parallel Processing (Euro-Par\u201996) . 352--358. Pilar de la Torre and Clyde P. Kruskal. 1996. Submachine locality in the bulk synchronous setting. In Proceedings of the 2nd International Conference on Parallel Processing (Euro-Par\u201996). 352--358."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76362"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294141"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90399-2"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/322003.322015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/290409.290412"},{"key":"e_1_2_1_35_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1973. The Art of Computer Programming, Volume III: Sorting and Searching ( 2 nd ed.). Addison-Wesley . Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching (2nd ed.). Addison-Wesley.","edition":"2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256299"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224157"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Frank T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann.   Frank T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277681"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216044"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344551.1344563"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033094.2033106"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/646714.701412"},{"volume-title":"Models of Computation: Exploring the Power of Computing","author":"Savage John E.","key":"e_1_2_1_44_1","unstructured":"John E. Savage . 1998. Models of Computation: Exploring the Power of Computing . Addison-Wesley Longman Publishing Co., Inc. John E. Savage. 1998. Models of Computation: Exploring the Power of Computing. Addison-Wesley Longman Publishing Co., Inc."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","author":"Scquizzato Michele","year":"2014","unstructured":"Michele Scquizzato and Francesco Silvestri . 2014 . Communication lower bounds for distributed-memory computations . In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS\u201914) . 627--638. Michele Scquizzato and Francesco Silvestri. 2014. Communication lower bounds for distributed-memory computations. In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS\u201914). 627--638."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00197-7"},{"volume-title":"Encyclopedia of Parallel Computing","author":"Tiskin Alexander","key":"e_1_2_1_48_1","unstructured":"Alexander Tiskin . 2011. BSP (bulk synchronous parallelism). In Encyclopedia of Parallel Computing . Springer , 192--199. Alexander Tiskin. 2011. BSP (bulk synchronous parallelism). In Encyclopedia of Parallel Computing. Springer, 192--199."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676221"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675790"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3181776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3181776","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3181776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:37:49Z","timestamp":1750282669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3181776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,30]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3181776"],"URL":"https:\/\/doi.org\/10.1145\/3181776","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2017,9,30]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}