{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:45:25Z","timestamp":1764841525007,"version":"3.32.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4-5","license":[{"start":{"date-parts":[[1996,10,1]],"date-time":"1996-10-01T00:00:00Z","timestamp":844128000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,10]]},"DOI":"10.1007\/bf01940878","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T10:46:47Z","timestamp":1122806807000},"page":"517-542","source":"Crossref","is-referenced-by-count":56,"title":["Efficient PRAM simulation on a distributed memory machine"],"prefix":"10.1007","volume":"16","author":[{"given":"R. M.","family":"Karp","sequence":"first","affiliation":[]},{"given":"M.","family":"Luby","sequence":"additional","affiliation":[]},{"given":"F.","family":"Meyer auf der Heide","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01940878_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1991","unstructured":"N. Alon and J. H. Spencer.The Probabilistic Method. Wiley, New York, 1991."},{"key":"BF01940878_CR2","doi-asserted-by":"crossref","unstructured":"H. Bast and T. Hagerup. Fast and reliable parallel hashing.Proc. 3rd Ann. ACM Symp. on Parallel Algorithms and Architectures, pages 50\u201361, 1991.","DOI":"10.1145\/113379.113384"},{"key":"BF01940878_CR3","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s.Random Graphs. Academic Press, London, 1985."},{"key":"BF01940878_CR4","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. L. Carter and M. N. Wegman. Universal classes of hash functions.J. Comput. System Sci., 18:143\u2013154, 1979.","journal-title":"J. Comput. System Sci."},{"key":"BF01940878_CR5","doi-asserted-by":"crossref","unstructured":"B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik. Efficient simulations between concurrent-read concurrent-write PRAM models.Proc. MFCS '88, pages 231\u2013239, 1988.","DOI":"10.1007\/BFb0017146"},{"key":"BF01940878_CR6","doi-asserted-by":"crossref","unstructured":"B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik. New simulations between CRCW PRAMs.Proc. MFCS '89, pages 95\u2013104, 1989.","DOI":"10.1007\/3-540-51498-8_9"},{"key":"BF01940878_CR7","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic Perfect Hashing: Upper and Lower Bounds. Technical Report 77, Universit\u00e4t-GH Paderborn, FB Mathematik-Informatik, Jan. 1991. (Revised version of paper with same title that appeared inProc. 24thIEEE FOCS, pages 524\u2013531, 1988.) To appear inSIAM J. Comput.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"BF01940878_CR8","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. How to distribute a hash table in a complete network.Proc. 22nd Ann. ACM Symp. on Theory of Computing, pages 117\u2013127, 1990.","DOI":"10.1145\/100216.100229"},{"key":"BF01940878_CR9","series-title":"Lecture Notes in Computer Science, Vol. 443","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BFb0032018","volume-title":"Proc. 17th ICALP","author":"M. Dietzfelbinger","year":"1990","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In M. S. Paterson, editor,Proc. 17th ICALP, pages 6\u201319, 1990. Lecture Notes in Computer Science, Vol. 443. Springer-Verlag, Berlin."},{"key":"BF01940878_CR10","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/0217037","volume":"17","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation.SIAM J. Comput., 17:606\u2013627, June 1988.","journal-title":"SIAM J. Comput."},{"key":"BF01940878_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01762109","volume":"3","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Simulations among concurrent-write PRAMs.Algorithmica, 3:43\u201351, 1988.","journal-title":"Algorithmica"},{"key":"BF01940878_CR12","unstructured":"J. Gil and Y. Matias. Fast hashing on a PRAM-designing by expectation.Proc. SODA '91, pages 271\u2013280, 1991."},{"key":"BF01940878_CR13","doi-asserted-by":"crossref","unstructured":"J. Gil and Y. Matias. Leaders election without a conflict resolution rule\u2014fast and efficient randomized simulations among CRCW PRAMs.Proc. LATIN '92, pages 204\u2013218, 1992.","DOI":"10.1007\/BFb0023830"},{"key":"BF01940878_CR14","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms.Proc. FOCS '91, pages 698\u2013710, Oct. 1991.","DOI":"10.1109\/SFCS.1991.185438"},{"key":"BF01940878_CR15","doi-asserted-by":"crossref","unstructured":"A. Karlin and E. Upfal. Parallel hashing\u2014an efficient implementation of shared memory.Proc. 18th Ann. ACM Symp. on Theory of Computing, pages 160\u2013168, 1986.","DOI":"10.1145\/12130.12146"},{"key":"BF01940878_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(90)90192-K","volume":"71","author":"C. P. Kruskal","year":"1990","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms.Theoret. Comput. Sci., 71:95\u2013132, 1990.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01940878_CR17","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. Converting high probability into nearly-constant time\u2014with applications to parallel hashing.Proc. 23rd Ann. ACM Symp. on Theory of Computing, pages 307\u2013316, 1991.","DOI":"10.1145\/103418.103453"},{"key":"BF01940878_CR18","series-title":"London Mathematical Society Lecture Note Series, Vol. 141","first-page":"148","volume-title":"Surveys in Combinatorics","author":"C. McDiarmid","year":"1989","unstructured":"C. McDiarmid. On the method of bounded differences. In J. Siemons, editor,Surveys in Combinatorics, pages 148\u2013188. London Mathematical Society Lecture Note Series, Vol. 141. Cambridge University Press, Cambridge, 1989."},{"key":"BF01940878_CR19","first-page":"339","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories.Ada Inform., 21:339\u2013374, 1984.","journal-title":"Ada Inform."},{"key":"BF01940878_CR20","doi-asserted-by":"crossref","unstructured":"A. G. Ranade. How to emulate shared memory.Proc. 28th IEEE Ann. Symp. on Foundations of Computer Science, pages 185\u2013194, 1987.","DOI":"10.1109\/SFCS.1987.32"},{"key":"BF01940878_CR21","doi-asserted-by":"crossref","unstructured":"A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications.Proc. 30th IEEE Ann. Symp. on Foundations of Computer Science, pages 20\u201325, 1989. Revised Version.","DOI":"10.1109\/SFCS.1989.63450"},{"issue":"3","key":"BF01940878_CR22","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1145\/828.1892","volume":"31","author":"E. Upfal","year":"1984","unstructured":"E. Upfal. Efficient schemes for parallel communication.J. Assoc. Comput. Mach., 31(3):507\u2013517, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940878_CR23","first-page":"943","volume-title":"Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, Chapter 18, pages 943\u2013971. Elsevier, Amsterdam, 1990."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940878.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01940878\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940878","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T21:22:33Z","timestamp":1735852953000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01940878"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":23,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["BF01940878"],"URL":"https:\/\/doi.org\/10.1007\/bf01940878","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}