{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:47Z","timestamp":1787337467535,"version":"build-2736575974"},"reference-count":24,"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":[[1998,1]]},"abstract":"<jats:p>Opticalcommunication is likely to significantly speed up parallel computation because the vast bandwidth of the optical medium can be divided to produce communication networks of very high degree. However, the problem of contention in high-degree networks makes the routing problem in these networks theoretically (and practically) difficult. In this paper we examine Valiant's h-relation routing problem, which is a fundamental problem in the theory of parallel computing. The h-relation routing problem arises both in the direct implementation of specific parallel algorithms on distributed-memory machines and in the general simulation of shared-memory models such as the PRAM on distributed-memory machines. In an h-relation routing problem each processor has up to h messages that it wishes to send to other processors and each processor is the destination of at most h messages. We present a lower bound for routing an h-relation (for any h &gt; 1) on a complete optical network of size n. Our lower bound applies to any randomized distributed algorithm for this task. Specifically, we show that the expected number of communication steps required to route an arbitrary h-relation is $\\Omega(h + \\sqrt{\\,\\log\\log n}\\,)$. This is the first known lower bound for this problem which does not restrict the class of algorithms under consideration.<\/jats:p>","DOI":"10.1137\/s0097539794272569","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1083-1098","source":"Crossref","is-referenced-by-count":3,"title":["An $\\Omega(\\sqrt{\\,\\log\\log n}\\,)$ Lower Bound for Routing in Optical Networks"],"prefix":"10.1137","volume":"27","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":"Philip D.","family":"MacKenzie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"R. J. Anderson and G. L. Miller,\n                      Optical Communication for Pointer Based Algorithms\n                      , Technical Report CRI 88\u201014, Computer Science Department, University of Southern California, Los Angeles, CA, 1988."},{"key":"R2","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide,\n                      Simple Efficient Shared Memory Simulations\n                      , in Symp. on Computer Architectures 5, 1993, pp. 110\u2013119."},{"key":"R3","unstructured":"P. W. Dowd,\n                      High performance interprocessor communication through optical wavelength division multiple access channels\n                      , Symp. on Computer Architectures 18, 1991, pp. 96\u2013105."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"R5","unstructured":"M. M. Eshaghian,\n                      Parallel Computing with Optical Interconnects\n                      , Ph.D. thesis, University of Southern California, Los Angeles, CA, Dec 1988."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/12.83620"},{"key":"R7","unstructured":"M. M. Eshaghian and V. K. P. Kumar,\n                      Optical arrays for parallel processing\n                      , in Proceedings of the Second Annual Parallel Processing Symposium, 1988, pp. 58\u201371."},{"key":"R8","unstructured":"Faith Fich, Friedhelm Meyer auf der Heide, Avi Wigderson, Lower bounds for parallel random\u2010access machines with unbounded shared memory, JAI, Greenwich, CT, 1987, 1\u20131589e:68031"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0217037"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"R11","unstructured":"Alexandros Gerbessiotis, Leslie Valiant, Direct bulk\u2010synchronous parallel algorithms, Lecture Notes in Comput. Sci., Vol. 621, Springer, Berlin, 1992, 1\u20131894f:68092"},{"key":"R12","unstructured":"M. Ger\u00e9b\u2010Graus and T. Tsantilas,\n                      Efficient optical communication in parallel computers\n                      , in Symposium on Parallel Algorithms and Architectures 4, 1992, pp. 41\u201348."},{"key":"R13","unstructured":"L. A. Goldberg, M. Jerrum, T. Leighton, and S. Rao,\n                      A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer\n                      , in Symposium on Parallel Algorithms and Architectures 5, 1993, pp. 300\u2013309."},{"key":"R14","unstructured":"V. Grolmusz and P. Ragde,\n                      Incomparability in parallel computation\n                      , in Foundations of Computer Science 28, 1987, pp. 89\u201398."},{"key":"R15","unstructured":"J. Hastad,\n                      Computational Limitations for Small Depth Circuits\n                      , MIT Press, Cambridge, MA, 1987."},{"key":"R16","unstructured":"R. Impagliazzo, R. Paturi, and M. E. Saks,\n                      Size\u2010depth trade\u2010offs for threshold circuits\n                      , in Symposium on Theory of Computing 25, 1993, pp. 541\u2013550."},{"key":"R17","unstructured":"M. Luby and B. Veli\u010dkovi\u0107,\n                      On deterministic approximation of DNF\n                      , in Symposium on Theory of Computing 23, 1991, pp. 430\u2013438."},{"key":"R18","unstructured":"P. D. MacKenzie,\n                      Load balancing requires \u03a9(log*n) expected time\n                      , in Symposium On Discrete Algorithms 3, 1992, pp. 94\u201399."},{"key":"R19","unstructured":"P. D. MacKenzie, C. G. Plaxton, and R. Rajaraman,\n                      On contention resolution protocols and associated probabilistic phenomena\n                      , in Symposium on Theoryof Computing 26, 1994, pp. 153\u2013162."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00199-0"},{"key":"R21","unstructured":"S. B. Rao,\n                      Properties of an Interconnection Architecture Based on Wavelength Division Multiplexing\n                      , Technical Report TR\u201092\u2010009\u20103\u20130054\u20102, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540, 1992."},{"key":"R22","unstructured":"L. G. Valiant,\n                      General purpose parallel architectures\n                      , Chapter 18 of\n                      Handbook of Theoretical Computer Science\n                      , J. van Leeuwen, Ed., Elsevier, New York, 1990;"},{"key":"R22","unstructured":"see especially p. 967."},{"key":"R23","unstructured":"A. C.\u2010C. Yao,\n                      Probabilistic computations: Toward a unified measure of complexity\n                      , in Proceedings of the 18th Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1977, pp. 222\u2013227."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794272569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:06Z","timestamp":1787335926000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794272569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794272569"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794272569","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}