{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:58:51Z","timestamp":1787385531315,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1997,8]]},"abstract":"<jats:p>In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h &gt; 1 requires $\\Theta(h + \\log p)$ expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for $h=\\Omega(\\log p)$, and it is an open question of Ger\u00e9b-Graus and Tsantilas whether there is a faster algorithm for h=o(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which $h\\leq \\log p$. In particular, we present a $\\Theta(h + \\log\\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if $h\\leq \\log p$, then the failure probability can be made as small as $p^{-\\alpha}$ for any positive constant $\\alpha$. We use the OCPC algorithm as a subroutine in a $\\Theta(h + \\log\\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a $p\\times p$-processor MOB-PC. Once again, we show that if $h\\leq \\log p$, then the failure probability can be made as small as $p^{-\\alpha}$ for any positive constant $\\alpha$.<\/jats:p>","DOI":"10.1137\/s0097539793259483","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1100-1119","source":"Crossref","is-referenced-by-count":23,"title":["Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers"],"prefix":"10.1137","volume":"26","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom","family":"Leighton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"J. Assoc. Comput. Mach., Lecture Notes in Comput. Sci. SIAM J. Comput., Proc. 2nd ACM\u2013SIAM Symposium on discrete algorithms, Proc. 4th ACM Symposium on Parallel Algorithms and Architectures, Proc. 23rd ACM Symposium on Theory of Computing Proc. 3rd Scandinavian Workshop on Algorithm Theory"},{"key":"R2","unstructured":"R. J. A nderson and G. L. M iller,\n                      Optical communication for pointer based algorithms\n                      , Technical Report CRI 88\u201014, Computer Science Department, University of Southern California, Los Angeles, 1988."},{"key":"R3","unstructured":"B. B ollob\u00e1s,\n                      Martingales, isoperimetric inequalities and random graphs\n                      , in Combinatorics, A. Hajnal, L. Lov\u00e1sz, and V. T. S\u00f3s, eds., Colloq. Math. Soc. J\u00e1nos Bolyai 52, North\u2013Holland, Amsterdam, 1988, pp. 113\u2013139."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. S. C hlebus, K. D iks, T. H agerup, and T. R adzik,\n                      New simulations between CRCW PRAMs\n                      , in Foundations of Computation Theory 7, lncs 380, Springer\u2010Verlag, Berlin, 1989, pp. 95\u2013104.","DOI":"10.1007\/3-540-51498-8_9"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"P. W. D owd,\n                      High performance interprocessor communication through optical wavelength division multiple access channels\n                      , in Proc. 18th ACM International Symposium on Computer Architecture, ACM, New York, 1991, pp. 96\u2013105.","DOI":"10.1145\/115952.115963"},{"key":"R7","unstructured":"M. M. E shaghian,\n                      Parallel computing with optical interconnects\n                      , Ph.D. thesis, University of Southern California, Los Angeles, 1988."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/12.83620"},{"key":"R9","unstructured":"M. M. E shaghian and V. K. P. K umar,\n                      Optical arrays for parallel processing\n                      , in Proc. 2nd International Symposium on Parallel Processing, IEEE Press, Piscataway, NJ, 1988, pp. 58\u201371."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. G er\u00e9b\u2010G raus and T. T santilas,\n                      Efficient optical communication in parallel computers\n                      , in Symposium on Parallel Algorithms and Architectures, ACM, New York, 1992, pp. 41\u201348.","DOI":"10.1145\/140901.140906"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. V. G erbessiotis and L. G. V aliant,\n                      Direct bulk\u2010synchronous parallel algorithms\n                      , in ScandinavianWorkshop on Algorithm Theory, Lecture Notes in Comput. Sci. 621, Springer\u2010Verlag, Berlin, 1992, pp. 1\u201318.","DOI":"10.1007\/3-540-55706-7_1"},{"key":"R12","unstructured":"J. G il and Y. M atias,\n                      Fast hashing on a PRAM\n                      , in Symposium\non discrete algorithms, SIAM, Philadelphia, 1991, pp. 271\u2013280."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Y. M atias and U. V ishkin,\n                      Converting high probability into nearly\u2010constant time: With applications to parallel hashing\n                      , in Symposium on Theory\nof Computing, ACM, New York, 1991, pp. 307\u2013316.","DOI":"10.1145\/103418.103453"},{"key":"R14","unstructured":"W. F. M cC oll,\n                      General purpose parallel computing\n                      , in Lectures on Parallel Computation, in Proc. 1991 ALCOM Spring School on Parallel Computation, A. M. Gibbons and P. Spirikas, eds., Cambridge University Press, Cambridge, UK, 1993, pp. 337\u2013391."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"C. M cD iarmid,\n                      On the method of bounded differences\n                      , in Surveys in Combinatorics, London Math. Soc. Lecture Notes Ser. 141, Cambridge University Press, Cambridge, UK, 1989, pp. 148\u2013188.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321882"},{"key":"R17","unstructured":"S. B. R ao,\n                      Properties of an interconnection architecture based on wavelength division multiplexing\n                      , Technical Report TR\u201092\u2010009\u20103\u20130054\u20102, NEC Research Institute, Princeton, NJ, 1992."},{"key":"R18","unstructured":"L. G. V aliant,\n                      General purpose parallel architectures\n                      , in Handbook of Theoretical Computer Science, J. van Leeuwen, ed., Elsevier, New York, 1990, Chapter 18 (see especially p. 967)."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675774"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793259483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:00Z","timestamp":1787335980000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793259483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,8]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,8]]}},"alternative-id":["10.1137\/S0097539793259483"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793259483","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,8]]}}}