{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:07Z","timestamp":1763467987196},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540233060"},{"type":"electronic","value":"9783540301868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30186-8_9","type":"book-chapter","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T19:48:23Z","timestamp":1285184903000},"page":"117-131","source":"Crossref","is-referenced-by-count":40,"title":["An Optimistic Approach to Lock-Free FIFO Queues"],"prefix":"10.1007","author":[{"given":"Edya","family":"Ladan-Mozes","sequence":"first","affiliation":[]},{"given":"Nir","family":"Shavit","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1145\/69624.357206","volume":"5","author":"A. Gottlieb","year":"1983","unstructured":"Gottlieb, A., Lubachevsky, B.D., Rudolph, L.: Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. ACM Trans. Program. Lang. Syst.\u00a05, 164\u2013189 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M. Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.: Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems\u00a012, 463\u2013492 (1990)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"9_CR3","volume-title":"Computer Architecture and Parallel Processing","author":"K. Hwang","year":"1990","unstructured":"Hwang, K., Briggs, F.A.: Computer Architecture and Parallel Processing. McGraw-Hill, Inc., New York (1990)"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1145\/69624.357207","volume":"5","author":"L. Lamport","year":"1983","unstructured":"Lamport, L.: Specifying concurrent program modules. ACM Transactions on Programming Languages and Systems\u00a05, 190\u2013222 (1983)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"unstructured":"Mellor-Crummey, J.M.: Concurrent queues: Practical fetch-and-\u03c6 algorithms. Technical Report Technical Report 229, University of Rochester (1987)","key":"9_CR5"},{"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)","key":"9_CR6"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1109\/12.280802","volume":"43","author":"S. Prakash","year":"1994","unstructured":"Prakash, S., Lee, Y.H., Johnson, T.: A non-blocking algorithm for shared queues using compare-and-swap. IEEE Transactions on Computers\u00a043, 548\u2013559 (1994)","journal-title":"IEEE Transactions on Computers"},{"key":"9_CR8","volume-title":"High-performance computer architecture","author":"H.S. Stone","year":"1987","unstructured":"Stone, H.S.: High-performance computer architecture. Addison-Wesley Longman Publishing Co., Inc., Amsterdam (1987)"},{"key":"9_CR9","first-page":"495","volume-title":"Proceedings of the 1990 conference on Supercomputing","author":"J. Stone","year":"1990","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 Press, Los Alamitos (1990)"},{"unstructured":"Treiber, R.K.: Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center (1986)","key":"9_CR10"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1145\/378580.378611","volume-title":"Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures","author":"P. Tsigas","year":"2001","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 Press, New York (2001)"},{"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":"9_CR12"},{"unstructured":"Lea, D.: (The java concurrency package (JSR-166)), \n                  \n                    http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest\/index.html","key":"9_CR13"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/248052.248106","volume-title":"Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC 1996)","author":"M.M. Michael","year":"1996","unstructured":"Michael, M.M., Scott, M.L.: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC 1996), pp. 267\u2013275. ACM, New York (1996)"},{"unstructured":"Craig, T.: Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02, University of Washington, Department of Computer Science (1993)","key":"9_CR15"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/IPPS.1994.288305","volume-title":"Proceedings of the 8th International Symposium on Parallel Processing (IPPS)","author":"P. Magnussen","year":"1994","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, Los Alamitos (1994)"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/103727.103729","volume":"9","author":"J. Mellor-Crummey","year":"1991","unstructured":"Mellor-Crummey, J., Scott, M.: Algorithms for scalable synchronization on sharedmemory multiprocessors. ACM Transactions on Computer Systems\u00a09, 21\u201365 (1991)","journal-title":"ACM Transactions on Computer Systems"},{"unstructured":"Weaver, D., T.G.: The SPARC Architecture Manual (Version 9). PTR Prentice Hall, Englewood Cliffs (1994)","key":"9_CR18"},{"unstructured":"Intel: Pentium Processor Family User\u2019s Manual: Vol 3, Architecture and Programming Manual (1994)","key":"9_CR19"},{"key":"9_CR20","doi-asserted-by":"publisher","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., Steele, G.: DCAS-based concurrent deques. Theory of Computing Systems\u00a035, 349\u2013386 (2002)","journal-title":"Theory of Computing Systems"},{"doi-asserted-by":"crossref","unstructured":"Luchangco, V., Moir, M., Shavit, N.: On the uncontended complexity of consensus. In: Proceedings of Distributed Computing (2003)","key":"9_CR21","DOI":"10.1007\/978-3-540-39989-6_4"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1109\/ICDCS.2003.1203503","volume-title":"Proceedings of the 23rd International Conference on Distributed Computing Systems","author":"M. Herlihy","year":"2003","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Doubleended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, pp. 522\u2013529. IEEE, Los Alamitos (2003)"},{"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)","key":"9_CR23","DOI":"10.1109\/MICRO.2001.991127"},{"key":"9_CR24","first-page":"339","volume-title":"Proceedings of the 16th International Symposium on DIStributed Computing","author":"M. Herlihy","year":"2002","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.\u00a02508, pp. 339\u2013353. Springer, Heidelberg (2002); A improved version of this paper is in preparation for journal submission; please contact authors"},{"key":"9_CR25","first-page":"21","volume-title":"The 21st Annual ACM Symposium on Principles of Distributed Computing","author":"M. Michael","year":"2002","unstructured":"Michael, M.: Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In: The 21st Annual ACM Symposium on Principles of Distributed Computing, pp. 21\u201330. ACM Press, New York (2002)"},{"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)","key":"9_CR26","DOI":"10.1145\/259380.259442"},{"key":"9_CR27","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/93385.93394","volume-title":"Proceedings of the 9th Annual ACM Symposium on Principles of Distribted Computing","author":"Y. Afek","year":"1990","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. In: Dwork, C. (ed.) Proceedings of the 9th Annual ACM Symposium on Principles of Distribted Computing, Qu\u00e9bec City, Qu\u00e9bec, Canada, pp. 1\u201314. ACM Press, New York (1990)"},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS)\u00a013, 124\u2013149 (1991)","journal-title":"ACM Transactions on Programming Languages and Systems (TOPLAS)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30186-8_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:53:33Z","timestamp":1620014013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30186-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540233060","9783540301868"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30186-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}