{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:53:09Z","timestamp":1794336789463,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540616276","type":"print"},{"value":"9783540706366","type":"electronic"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"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":[[1996]]},"DOI":"10.1007\/bfb0024714","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:17:56Z","timestamp":1132366676000},"page":"277-292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The queue-read queue-write asynchronous PRAM model"],"prefix":"10.1007","author":[{"given":"Phillip B.","family":"Gibbons","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yossi","family":"Matias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"issue":"1","key":"37_CR1","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1145\/151646.151651","volume":"15","author":"Y. Afek","year":"1993","unstructured":"Y. Afek, G. M. Brown, and M. Merritt. Lazy caching. ACM Trans. on Programming Languages and Systems, 15(1):182\u2013205, 1993.","journal-title":"ACM Trans. on Programming Languages and Systems"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"M. Adler. Asynchronous shared memory search structures. In Proc. 8th ACM Symp. on Parallel Algorithms and Architectures, June 1996. To appear.","DOI":"10.1145\/237502.237506"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"C. Armen and D. B. Johnson. Deterministic leader election on the Asynchronous QRQW PRAM. Parallel Processing Letters, 1996. To appear.","DOI":"10.1142\/S0129626496000248"},{"issue":"1","key":"37_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi. Sorting inclg n parallel steps. Combinatorica, 3(1):1\u201319, 1983.","journal-title":"Combinatorica"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"R. J. Anderson. Primitives for asynchronous list compression. In Proc. 4th ACM Symp. on Parallel Algorithms and Architectures, pages 199\u2013208, June\u2013July 1992.","DOI":"10.1145\/140901.140922"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"G. E. Blelloch, P. B. Gibbons, Y. Matias, and M. Zagha. Accounting for memory bank contention and delay in high-bandwidth multiprocessors. In Proc. 7th ACM Symp. on Parallel Algorithms and Architectures, pages 84\u201394, July 1995.","DOI":"10.1145\/215399.215425"},{"issue":"4","key":"37_CR7","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770\u2013785, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"R. Cole and O. Zajicek. The APRAM: Incorporating asynchrony into the PRAM model. In Proc. 1st ACM Symp. on Parallel Algorithms and Architectures, pages 169\u2013178, June 1989.","DOI":"10.1145\/72935.72954"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Herlihy, and O. Waarts. Contention in shared memory algorithms. In Proc. 25th ACM Symp. on Theory of Computing, pages 174\u2013183, May 1993.","DOI":"10.1145\/167088.167145"},{"issue":"2","key":"37_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0022-0000(05)80003-0","volume":"48","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, M. Kuty\u0142owski, and R. Reischuk. Exact lower time bounds for computing boolean functions on CREW PRAMs. Journal of Computer and System Sciences, 48(2):231\u2013254, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"37_CR11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1109\/TC.1983.1676201","volume":"C-32","author":"A. Gottlieb","year":"1983","unstructured":"A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir. The NYU Ultracomputer \u2014 designing an MIMD shared memory parallel computer. IEEE Trans. on Computers, C-32(2):175\u2013189, 1983.","journal-title":"IEEE Trans. on Computers"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons. A more practical PRAM model. In Proc. 1st ACM Symp. on Parallel Algorithms and Architectures, pages 158\u2013168, June 1989. Full version in The Asynchronous PRAM: A semi-synchronous model for shared memory MIMD machines, PhD thesis, U.C. Berkeley 1989.","DOI":"10.1145\/72935.72953"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, and J. Hennessy. Memory consistency and event ordering in scalable sharedmemory multiprocessors. In Proc. 17th International Symp. on Computer Architecture, pages 15\u201326, May 1990.","DOI":"10.1145\/325096.325102"},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons and M. Merritt. Specifying nonblocking shared memories. In Proc. 4th ACM Symp. on Parallel Algorithms and Architectures, pages 306\u2013315, June\u2013July 1992.","DOI":"10.1145\/140901.141895"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons, M. Merritt, and K. Gharachorloo. Proving sequential consistency of high-performance shared memories. In Proc. 3rd ACM Symp. on Parallel Algorithms and Architectures, pages 292\u2013303, July 1991.","DOI":"10.1145\/113379.113406"},{"key":"37_CR16","volume-title":"Technical report","author":"P. B. Gibbons","year":"1993","unstructured":"P. B. Gibbons, Y. Matias, and V. Ramachandran. QRQW: Accounting for concurrency in PRAMs and Asynchronous PRAMs. Technical report, AT&T Bell Laboratories, Murray Hill, NJ, March 1993."},{"key":"37_CR17","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons, Y. Matias, and V. Ramachandran. Efficient low-contention parallel algorithms. Journal of Computer and System Sciences, 1996. To appear. Preliminary version appears in Proc. 6th ACM Symp. on Parallel Algorithms and Architectures, pages 236\u2013247, June 1994.","DOI":"10.1145\/181014.181382"},{"key":"37_CR18","unstructured":"P. B. Gibbons, Y. Matias, and V. Ramachandran. The Queue-Read Queue-Write PRAM model: Accounting for contention in parallel algorithms. SIAM Journal on Computing, 1996. To appear. Preliminary version appears in Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, pages 638\u2013648, January 1994."},{"key":"37_CR19","volume-title":"Technical report","author":"P.B. Gibbons","year":"1996","unstructured":"P.B. Gibbons, Y. Matias, and V. Ramachandran. The queue-read queuewrite asynchronous PRAM model. Technical report, Bell Laboratories, Murray Hill, NJ, and Dept. of Comp. Sci., Univ. of Texas, Austin, TX, June 1996."},{"key":"37_CR20","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J. J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA, 1992."},{"key":"37_CR21","first-page":"869","volume-title":"Handbook of Theoretical Computer Science, Volume A","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A, pages 869\u2013941. Elsevier Science Publishers B.V., Amsterdam, The Netherlands, 1990."},{"key":"37_CR22","doi-asserted-by":"crossref","unstructured":"P. Liu, W. Aiello, and S. Bhatt. An atomic model for message-passing. In Proc. 5th ACM Symp. on Parallel Algorithms and Architectures, pages 154\u2013163, June\u2013July 1993.","DOI":"10.1145\/165231.165251"},{"issue":"9","key":"37_CR23","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1109\/TC.1979.1675439","volume":"C-28","author":"L. Lamport","year":"1979","unstructured":"L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. on Computers, C-28(9):690\u2013691, 1979.","journal-title":"IEEE Trans. on Computers"},{"issue":"6","key":"37_CR24","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1137\/0221063","volume":"21","author":"C. Martel","year":"1992","unstructured":"C. Martel, A. Park, and R. Subramonian. Work-optimal asynchronous algorithms for shared memory parallel computers. SIAM Journal on Computing, 21(6):1070\u20131099, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR25","doi-asserted-by":"crossref","unstructured":"N. Nishimura. Asynchronous shared memory parallel computation. In Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures, pages 76\u201384, July 1990.","DOI":"10.1145\/97444.97672"},{"issue":"2","key":"37_CR26","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1137\/0214030","volume":"14","author":"R. Reischuk","year":"1985","unstructured":"R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM Journal on Computing, 14(2):396\u2013409, May 1985.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR27","volume-title":"A Synthesis of Parallel Algorithms","year":"1993","unstructured":"J. H. Reif, editor. A Synthesis of Parallel Algorithms. Morgan-Kaufmann, San Mateo, CA, 1993."},{"key":"37_CR28","unstructured":"B. Smith. Invited lecture, 7th ACM Symp. on Parallel Algorithms and Architectures, July 1995."},{"key":"37_CR29","volume-title":"Technical Report 61","author":"U. Vishkin","year":"1983","unstructured":"U. Vishkin. On choice of a model of parallel computation. Technical Report 61, Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, 251 Mercer St., New York, NY 10012, 1983."}],"container-title":["Lecture Notes in Computer Science","Euro-Par'96 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,19]],"date-time":"2020-04-19T20:33:05Z","timestamp":1587328385000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616276","9783540706366"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/bfb0024714","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0024677","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"10 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}