{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:44Z","timestamp":1787337584931,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the PRAM(m) model, where p processors communicate through a globally shared memory which can service m requests per unit time, we focus on the trade-off between the amount of local computation and the amount of interprocessor communication required for parallel sorting algorithms. Our main result is a lower bound of $\\Omega(\\frac{n \\log m}{m \\log n})$ on the time required to sort n numbers on the exclusive-read and queued-read variants of the PRAM(m). We also show that Leighton's Columnsort can be used to give an asymptotically matching upper bound in the case where m grows as a fractional power of n. The bounds are of a surprising form in that they have little dependence on the parameter p. This implies that attempting to distribute the workload across more processors while holding the problem size and the size of the shared memory fixed will not improve the optimal running time of sorting in this model. We also show that both the lower and the upper bounds can be adapted to bridging models that address the issue of limited communication bandwidth: the LogP model and the bulk-synchronous parallel (BSP) model. The lower bounds provide further convincing evidence that efficient parallel algorithms for sorting rely strongly on high communication bandwidth.<\/jats:p>","DOI":"10.1137\/s0097539797315884","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1997-2015","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Sorting with Limited Bandwidth"],"prefix":"10.1137","volume":"29","author":[{"given":"Micah","family":"Adler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John W.","family":"Byers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard M.","family":"Karp","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Micah Adler, New coding techniques for improved bandwidth utilization, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 173\u20131821450615","DOI":"10.1109\/SFCS.1996.548476"},{"key":"R2","doi-asserted-by":"crossref","first-page":"1997","DOI":"10.1137\/S0097539797315884","volume":"29","author":"Adler Micah","year":"2000","journal-title":"SIAM J. Comput."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90188-N"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. Chandra, and M. Snir,\n                      Hierarchical memory with block transfer\n                      , in Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, 1987, pp. 204\u2013216.","DOI":"10.1109\/SFCS.1987.31"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. Chandra, and M. Snir,\n                      On communication latency in PRAM computations\n                      , in Proceedings of the First ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, 1989.","DOI":"10.1145\/72935.72937"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Alok Aggarwal, Ming\u2010Deh Huang, Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks (preliminary version), Lecture Notes in Comput. Sci., Vol. 319, Springer, New York, 1988, 339\u20133501017485","DOI":"10.1007\/BFb0040401"},{"key":"R7","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0221024"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2649"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"G. Blelloch, P. Gibbons, Y. Matias, and M. Zagha,\n                      Accounting for memory bank contention and delay in high\u2010bandwidth multiprocessors\n                      , in Proceedings of the Seventh ACM Symposium on Parallel Algorithms and Architectures, Santa Barbara, CA, 1995, pp. 84\u201394.","DOI":"10.1145\/215399.215425"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0211022"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0215006"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/240455.240477"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90016-6"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/71.532111"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90059-X"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0217037"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Gerbessiotis and C. Siniolakis,\n                      Deterministic sorting and randomized median finding on the BSP model\n                      , in Proceedings of the Eighth ACM Symposium on Parallel Algorithms and Architectures, Padua, Italy, 1996, pp. 223\u2013232.","DOI":"10.1145\/237502.237561"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1085"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979427491"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"P. Gibbons, Y. Matias, and V. Ramachandran,\n                      Efficient low\u2010contention parallel algorithms\n                      , in Proceedings of the Sixth ACM Symposium on Parallel Algorithms and Architectures, Cape May, NJ, 1994, pp. 236\u2013247.","DOI":"10.1145\/181014.181382"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Michael Goodrich, Communication\u2010efficient parallel sorting (preliminary version), ACM, New York, 1996, 247\u20132561427520","DOI":"10.1145\/237814.237870"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Richard Karp, Vijaya Ramachandran, Parallel algorithms for shared\u2010memory machines, Elsevier, Amsterdam, 1990, 869\u20139411127183","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.5009385"},{"key":"R27","volume-title":"Introduction to parallel algorithms and architectures","author":"Leighton F.","year":"1992"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"M. Li and Y. Yesha,\n                      Separation and lower bounds for ROM and non\u2010deterministic models of parallel computation\n                      , in Proceedings of the 18th ACM Symposium on Theory of Computing, Berkeley, CA, 1986, pp. 177\u2013187.","DOI":"10.1145\/12130.12148"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"P. Mackenzie,\n                      Lower bounds for randomized exclusive write PRAMs\n                      , in Proceedings of the Seventh ACM Symposium on Parallel Algorithms and Architectures, Santa Barbara, CA, 1995, pp. 254\u2013263.","DOI":"10.1145\/215399.215454"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Y. Mansour, N. Nisan, and U. Vishkin,\n                      Trade\u2010offs between communication throughput and parallel time\n                      , in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 1994, pp. 372\u2013381.","DOI":"10.1145\/195058.195199"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264615"},{"key":"R32","unstructured":"C. Thompson,\n                      A Complexity Theory for VLSI\n                      , Ph.D. thesis., Carnegie\u2010Mellon University, Pittsburgh, PA, 1980."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"L. Valiant, General purpose parallel architectures, Elsevier, Amsterdam, 1990, 943\u20139711127184","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/0214024"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"A. Yao,\n                      Probabilistic computations: Toward a unified measure of complexity\n                      , in Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, Providence, RI, 1977, pp. 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797315884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:13Z","timestamp":1787336353000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797315884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539797315884"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797315884","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}