{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:36Z","timestamp":1787337576996,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>In this paper we study the problem of simulating shared memory on the distributed memory machine (DMM). Our approach uses multiple copies of shared memory cells, distributed among the memory modules of the DMM via universal hashing. The main aim is to design strategies that resolve contention at the memory modules. Extending results and methods from random graphs and very fast randomized algorithms, we present new simulation techniques that enable us to improve the previously best results exponentially. In particular, we show that an n-processor CRCW PRAM can be simulated by an n-processor DMM with delay $\\O(\\log\\log\\log n \\log^*n)$, with high probability.<\/jats:p>\n                  <jats:p>\n                    Next we describe a general technique that can be used to turn these simulations into time-processor optimal ones, in the case of EREW PRAMs to be simulated. We obtain a time-processor optimal simulation of an (n log log log n log\n                    <jats:sup>*<\/jats:sup>\n                    n )-processor EREW PRAM on an n-processor DMM with delay $\\O(\\log\\log\\log n \\log^*n)$, with high probability. When an (n log log log n log\n                    <jats:sup>*<\/jats:sup>\n                    n )-processor CRCW PRAM is simulated, the delay is only by a log\n                    <jats:sup>*<\/jats:sup>\n                    n factor larger.\n                  <\/jats:p>\n                  <jats:p>We further demonstrate that the simulations presented can not be significantly improved using our techniques. We show an $\\Omega(\\log\\log\\log n \/ \\log\\log\\log\\log n)$ lower bound on the expected delay for a class of PRAM simulations, called topological simulations, that covers all previously known simulations as well as the simulations presented in the paper.<\/jats:p>","DOI":"10.1137\/s009753979529564x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1703-1739","source":"Crossref","is-referenced-by-count":14,"title":["Contention Resolution in Hashing Based Shared Memory Simulations"],"prefix":"10.1137","volume":"29","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedhelm Meyer auf","family":"Heide","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Stemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"R. J. Anderson and G. L. Miller,\n                      Optical Communication for Pointer Based Algorithms\n                      , Tech. Report CRI 88\u201014, University of Southern California, Los Angeles, CA, 1988."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"H. Bast and T. Hagerup,\n                      Fast and reliable parallel hashing\n                      , in Proc. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, ACM Press, New York, NY, 1991, pp. 50\u201361.","DOI":"10.1145\/113379.113384"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1159"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide,\n                      How to distribute a dictionary in a complete network\n                      , in Proc. 22nd Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, 1990, pp. 117\u2013127.","DOI":"10.1145\/100216.100229"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide,\n                      Simple, efficient shared memory simulations\n                      , in Proc. 5th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM Press, New York, NY, 1993, pp. 110\u2013119.","DOI":"10.1145\/165231.165246"},{"key":"R9","first-page":"17","volume":"5","author":"Erd\u00f6s P.","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Joseph Gil, Yossi Matias, Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, 698\u20137101177216","DOI":"10.1109\/SFCS.1991.185438"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259483"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290507"},{"key":"R13","unstructured":"M. T. Goodrich, Y. Matias, and U. Vishkin,\n                      Optimal parallel approximation algorithms for prefix sums and integer sorting\n                      , in Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press, New York, NY, 1994, pp. 241\u2013250."},{"key":"R14","unstructured":"Torben Hagerup, The log\u2010star revolution, Lecture Notes in Comput. Sci., Vol. 577, Springer, Berlin, 1992, 259\u201327894j:68060"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"R16","volume-title":"Introduction to parallel algorithms and architectures","author":"Leighton F.","year":"1992"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/48014.350550"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran,\n                      A survey of parallel algorithms for shared\u2010memory machines\n                      , in Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. van Leeuwen, ed., Elsevier Science, Amsterdam, The Netherlands, 1990, pp. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900063"},{"key":"R20","volume-title":"Introduction to parallel algorithms and architectures","author":"Leighton F.","year":"1992"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Tom Leighton, Methods for message routing in parallel machines, Birkh\u00e4user, Basel, 1995, 1417\u201301404043","DOI":"10.1007\/978-3-0348-9078-6_136"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274816"},{"key":"R23","unstructured":"Colin McDiarmid, On the method of bounded differences, London Math. Soc. Lecture Note Ser., Vol. 141, Cambridge Univ. Press, Cambridge, 1989, 148\u201318891e:05077"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264615"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00032-1"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1019"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90005-P"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"G. Megson, L. Rapanotti, X. Chen, Automatic synthesis of parallel algorithms, Lecture Notes in Comput. Sci., Vol. 1054, Springer, Berlin, 1996, 51\u20138697g:68086","DOI":"10.1007\/BFb0027118"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"A. Siegel,\n                      On universal classes of fast high performance hash functions, their time\u2010space tradeoff, and their applications\n                      , in Proc. 30th IEEE Symposium on Foundations of Computer Science, IEEE Press, Los Alamitos, CA, 1989, pp. 20\u201325.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"R30","doi-asserted-by":"crossref","first-page":"1703","DOI":"10.1137\/S009753979529564X","volume":"29","author":"Czumaj Artur","year":"2000","journal-title":"SIAM J. Comput."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/828.1892"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7926"},{"key":"R33","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"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753979529564X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:46Z","timestamp":1787336326000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753979529564X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S009753979529564X"],"URL":"https:\/\/doi.org\/10.1137\/s009753979529564x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}