{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:46:28Z","timestamp":1764402388591},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T00:00:00Z","timestamp":1196380800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s00446-007-0050-0","type":"journal-article","created":{"date-parts":[[2007,11,29]],"date-time":"2007-11-29T13:41:36Z","timestamp":1196343696000},"page":"323-341","source":"Crossref","is-referenced-by-count":26,"title":["An optimistic approach to lock-free FIFO queues"],"prefix":"10.1007","volume":"20","author":[{"given":"Edya","family":"Ladan-Mozes","sequence":"first","affiliation":[]},{"given":"Nir","family":"Shavit","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,11,30]]},"reference":[{"issue":"4","key":"50_CR1","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y. Afek","year":"1993","unstructured":"Afek Y., Attiya H., Dolev D., Gafni E., Merritt M. and Shavit N. (1993). Atomic snapshots of shared memory. J. ACM. 40(4): 873\u2013890","journal-title":"J. ACM."},{"issue":"3","key":"50_CR2","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s00224-002-1058-2","volume":"35","author":"O. Agesen","year":"2002","unstructured":"Agesen O., Detlefs D., Flood C., Garthwaite A., Martin P., Moir M., Shavit N. and Steele G. (2002). DCAS-based concurrent deques. Theo. Comput. Syst. 35(3): 349\u2013386","journal-title":"Theo. Comput. Syst."},{"key":"50_CR3","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen T., Leiserson C., Rivest R. and Stein C. (2001). Introduction to Algorithms, 2nd edn. MIT Press, Cambridge","edition":"2"},{"key":"50_CR4","unstructured":"Craig, T.: Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02, Department of Computer Science, University of Washington (1993)"},{"issue":"2","key":"50_CR5","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1145\/69624.357206","volume":"5","author":"A. Gottlieb","year":"1983","unstructured":"Gottlieb A., Lubachevsky B.D. and Rudolph L. (1983). Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. ACM Trans. Progr. Lang. Syst. 5(2): 164\u2013189","journal-title":"ACM Trans. Progr. Lang. Syst."},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Martin, P., Moir, M.: Dynamic-sized lock-free data structures. In: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing, pp. 131\u2013131. ACM, New York (2002)","DOI":"10.1145\/571825.571847"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: The repeat offender problem: A mechanism for supporting lock-free dynamic-sized data structures. In: Proceedings of the 16th International Symposium on Distributed Computing, vol. 2508, pp. 339\u2013353. Springer, Heidelberg (2002). A improved version of this paper is in preparation for journal submission","DOI":"10.1007\/3-540-36108-1_23"},{"key":"50_CR8","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, pp. 522\u2013529. IEEE (2003)","DOI":"10.1109\/ICDCS.2003.1203503"},{"issue":"3","key":"50_CR9","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M.P. Herlihy","year":"1990","unstructured":"Herlihy M.P. and Wing J.M. (1990). Linearizability: a correctness condition for concurrent objects. ACM Trans. Progr. Lang. Syst. (TOPLAS) 12(3): 463\u2013492","journal-title":"ACM Trans. Progr. Lang. Syst. (TOPLAS)"},{"key":"50_CR10","volume-title":"Computer Architecture and Parallel Processing","author":"K. Hwang","year":"1990","unstructured":"Hwang K. and Briggs F.A. (1990). Computer Architecture and Parallel Processing. McGraw-Hill, New York"},{"key":"50_CR11","unstructured":"Intel. Pentium Processor Family User\u2019s Manual: vol 3. In: Architecture and Programming Manual, 1994"},{"issue":"2","key":"50_CR12","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1145\/69624.357207","volume":"5","author":"L. Lamport","year":"1983","unstructured":"Lamport L. (1983). Specifying concurrent program modules. ACM Trans. Progr. Lang. Syst. 5(2): 190\u2013222","journal-title":"ACM Trans. Progr. Lang. Syst."},{"key":"50_CR13","unstructured":"Lea, D.: The java concurrency package (JSR-166). http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest\/index.html"},{"key":"50_CR14","unstructured":"Lea, D.: The java.util.concurrent synchronizer framework. In: Workshop on Concurrency and Synchronization in Java Programs, pp. 1\u20139 (2004)"},{"key":"50_CR15","doi-asserted-by":"crossref","unstructured":"Luchangco, V., Moir, M., Shavit, N.: On the uncontended complexity of consensus. In: Proceedings of the 17th International Conference on Distributed Computing, pp. 45\u201359 (2003)","DOI":"10.1007\/978-3-540-39989-6_4"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"Magnussen, P., Landin, A., Hagersten, E.: Queue locks on cache coherent multiprocessors. In: Proceedings of the 8th International Symposium on Parallel Processing (IPPS), pp. 165\u2013171. IEEE Computer Society (1994)","DOI":"10.1109\/IPPS.1994.288305"},{"issue":"1","key":"50_CR17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/103727.103729","volume":"9","author":"J. Mellor-Crummey","year":"1991","unstructured":"Mellor-Crummey J. and Scott M. (1991). Algorithms for scalable synchronization on shared\u2014memory multiprocessors. ACM Trans. Comput. Syst. 9(1): 21\u201365","journal-title":"ACM Trans. Comput. Syst."},{"key":"50_CR18","unstructured":"Mellor-Crummey, J.M.: Concurrent queues: Practical fetch-and-\u03c6 algorithms. Technical Report 229, University of Rochester (1987)"},{"issue":"1","key":"50_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jpdc.1998.1446","volume":"51","author":"M. Michael","year":"1998","unstructured":"Michael M. and Scott M. (1998). Nonblocking algorithms and preemption-safe locking on multiprogrammed shared\u2014memory multiprocessors. J. Parallel Distrib. Comput. 51(1): 1\u201326","journal-title":"J. Parallel Distrib. Comput."},{"issue":"6","key":"50_CR20","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1109\/TPDS.2004.8","volume":"15","author":"M.M. Michael","year":"2004","unstructured":"Michael M.M. (2004). Hazard pointers: safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst. 15(6): 491\u2013504","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"50_CR21","doi-asserted-by":"crossref","unstructured":"Moir, M.: Practical implementations of non-blocking synchronization primitives. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 219\u2013228 (1997)","DOI":"10.1145\/259380.259442"},{"key":"50_CR22","doi-asserted-by":"crossref","unstructured":"Moir, M., Shavit, N.: Chapter 47 \u2013 Concurrent Data Structures \u2013 Handbook of Data Structures and Applications, 1st edn. Chapman and Hall\/CRC, London (2004)","DOI":"10.1201\/9781420035179.ch47"},{"key":"50_CR23","unstructured":"Prakash, S., Lee, Y.-H., Johnson, T.: Non-blocking algorithms for concurrent data structures. Technical Report 91\u2013002, Department of Information Sciences, University of Florida (1991)"},{"issue":"5","key":"50_CR24","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1109\/12.280802","volume":"43","author":"S. Prakash","year":"1994","unstructured":"Prakash S., Lee Y.-H. and Johnson T. (1994). A non-blocking algorithm for shared queues using compare-and-swap. IEEE Trans. Comput. 43(5): 548\u2013559","journal-title":"IEEE Trans. Comput."},{"key":"50_CR25","doi-asserted-by":"crossref","unstructured":"Rajwar, R., Goodman, J.: Speculative lock elision: enabling highly concurrent multithreaded execution. In: Proceedings of the 34th Annual International Symposium on Microarchitecture, pp. 294\u2013305 (2001)","DOI":"10.1109\/MICRO.2001.991127"},{"key":"50_CR26","doi-asserted-by":"crossref","unstructured":"Scherer, W.N., Scott, M.L.: Nonblocking concurrent data structures with condition synchronization. In: Proceedings of the 18th International Symposium on Distributed Computing, pp. 174\u2013187. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-30186-8_13"},{"key":"50_CR27","volume-title":"High-performance Computer Architecture","author":"H.S. Stone","year":"1987","unstructured":"Stone H.S. (1987). High-performance Computer Architecture. Addison-Wesley Longman, Reading"},{"key":"50_CR28","doi-asserted-by":"crossref","unstructured":"Stone, J.: A simple and correct shared-queue algorithm using compare-and-swap. In:Proceedings of the 1990 Conference on Supercomputing, pp. 495\u2013504. IEEE Computer Society","DOI":"10.1109\/SUPERC.1990.130060"},{"key":"50_CR29","unstructured":"Treiber, R.K.: Systems programming: coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center (1986)"},{"key":"50_CR30","doi-asserted-by":"crossref","unstructured":"Tsigas, P., Zhang, Y.: A simple, fast and scalable non-blocking concurrent fifo queue for shared memory multiprocessor systems. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 134\u2013143. ACM, New york (2001)","DOI":"10.1145\/378580.378611"},{"key":"50_CR31","unstructured":"Valois, J.: Implementing lock-free queues. In: Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, pp. 64\u201369 (1994)"},{"key":"50_CR32","doi-asserted-by":"crossref","unstructured":"Valois, J.D.: Lock-free linked lists using compare-and-swap. In: Symposium on Principles of Distributed Computing, pp. 214\u2013222 (1995)","DOI":"10.1145\/224964.224988"},{"key":"50_CR33","volume-title":"The SPARC Architecture Manual Version 9","author":"D. Weaver","year":"1994","unstructured":"Weaver D. and Germond T. (1994). The SPARC Architecture Manual Version 9. Prentice Hall, Englewood Cliffs"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0050-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-007-0050-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0050-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:37Z","timestamp":1559136397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-007-0050-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,30]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["50"],"URL":"https:\/\/doi.org\/10.1007\/s00446-007-0050-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,30]]}}}