{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:03:16Z","timestamp":1787385796347,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540603139","type":"print"},{"value":"9783540449133","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60313-1_133","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:17:37Z","timestamp":1330262257000},"page":"46-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Shared memory simulations with triple-logarithmic delay"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Stemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"4_CR1","series-title":"Constant-Time Parallel Integer Sorting","volume-title":"Technical Report MPI-I-93-123","author":"H. Bast","year":"1993","unstructured":"H. Bast and T. Hagerup. Fast parallel space allocation, estimation and integer sorting (revised). Technical Report MPI-I-93-123, Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald 66123 Saarbr\u00fccken, June 1993. A preliminary version appeared in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing under the title \u201cConstant-Time Parallel Integer Sorting\u201d, 1991."},{"issue":"2","key":"4_CR2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"O. Berkman and U. Vishkin. Recursive star-tree parallel data structure. SIAM Journal on Computing, 22(2):221\u2013242, 1993. A preliminary version appeared in Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 196\u2013202, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR3","unstructured":"A. Czumaj, F. Meyer auf der Heide, and V. Stemann. Improved optimal shared memory simulations, and the power of reconfiguration. To appear in Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems, 1995."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proceedings of the 17th Annual International Colloquium on Automata, Languages and Programming, pages 6\u201319, 1990.","DOI":"10.1007\/BFb0032018"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. Simple, efficient shared memory simulations. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 110\u2013119, 1993.","DOI":"10.1145\/165231.165246"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"L. A. Goldberg, Y. Matias, and S. Rao. An optical simulation of shared memory. In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 257\u2013267, 1994.","DOI":"10.1145\/181014.181406"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 698\u2013710, 1991.","DOI":"10.1109\/SFCS.1991.185438"},{"key":"4_CR8","unstructured":"M. T. Goodrich, Y. Matias, and U. Vishkin. Optimal parallel approximation algorithms for prefix sums and integer sorting. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 241\u2013250, 1994."},{"key":"4_CR9","unstructured":"J. J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison Wesley, 1992."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby, and F. Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Technical Report tr-ri-93-134, University of Paderborn, 1993, to appear in Algorithmica. A preliminary version appeared in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 318\u2013326, 1992.","DOI":"10.1145\/129712.129743"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"A. Karlin and E. Upfal. Parallel hashing \u2014 an efficient implementation of shared memory. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 160\u2013168, 1986.","DOI":"10.1145\/12130.12146"},{"key":"4_CR12","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F. T. Leighton","year":"1992","unstructured":"F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, San Mateo, 1992."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"F. T. Leighton. Methods for packet routing in parallel machines. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 77\u201396, 1992.","DOI":"10.1145\/129712.129721"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide. Hashing strategies for simulating shared memory on distributed memory machines. In Proceedings of the Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, pages 20\u201329, 1992.","DOI":"10.1007\/3-540-56731-3_3"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"P. D. MacKenzie, C. G. Plaxton, and R. Rajaraman. On contention resolution protocols and associated probabilistic phenomena. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 153\u2013162, 1994.","DOI":"10.1145\/195058.195122"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, C. Scheideler, and V. Stemann. Exploiting storage redundancy to speed up randomized shared memory simulations. To appear in Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, 1995.","DOI":"10.1016\/0304-3975(96)00032-1"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1006\/jagm.1993.1019","volume":"14","author":"P. Ragde","year":"1993","unstructured":"P. Ragde. The parallel simplicity of compaction and chaining. Journal of Algorithms, 14:371\u2013380, 1993.","journal-title":"Journal of Algorithms"},{"key":"4_CR18","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0022-0000(91)90005-P","volume":"42","author":"A. G. Ranade","year":"1991","unstructured":"A. G. Ranade. How to simulate shared memory. Journal of Computer and System Sciences, 42:307\u2013326, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 20\u201325, 1989.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1145\/828.1892","volume":"31","author":"E. Upfal","year":"1984","unstructured":"E. Upfal. Efficient schemes for parallel communication. Journal of the ACM, 31:507\u2013517, 1984.","journal-title":"Journal of the ACM"},{"key":"4_CR21","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/7531.7926","volume":"34","author":"E. Upfal","year":"1987","unstructured":"E. Upfal and A. Wigderson. How to share memory in a distributed system. Journal of the ACM, 34:116\u2013127, 1987.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T19:00:12Z","timestamp":1742583612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_133"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-60313-1_133","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}