{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T04:01:37Z","timestamp":1743998497888,"version":"3.40.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9420-5","type":"journal-article","created":{"date-parts":[[2012,7,31]],"date-time":"2012-07-31T09:35:49Z","timestamp":1343727349000},"page":"729-762","source":"Crossref","is-referenced-by-count":3,"title":["Built-in Coloring for Highly-Concurrent Doubly-Linked Lists"],"prefix":"10.1007","volume":"52","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[]},{"given":"Eshcar","family":"Hillel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,8,1]]},"reference":[{"key":"9420_CR1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1145\/259380.259431","volume-title":"Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"Y. Afek","year":"1997","unstructured":"Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a0111\u2013120 (1997)"},{"issue":"3","key":"9420_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.L., Flood, C.H., Garthwaite, A.T., Martin, P.A., Shavit, N., Steele, G.L.: DCAS-based concurrent deques. Theory Comput. Syst. 35(3), 349\u2013386 (2002)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9420_CR3","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00224-001-0004-z","volume":"34","author":"N.S. Arora","year":"2001","unstructured":"Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. Theory Comput. Syst. 34(2), 115\u2013144 (2001)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"9420_CR4","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1145\/502102.502105","volume":"48","author":"H. Attiya","year":"2001","unstructured":"Attiya, H., Dagan, E.: Improved implementations of binary universal operations. J. ACM 48(5), 1013\u20131037 (2001)","journal-title":"J. ACM"},{"issue":"12\u201314","key":"9420_CR5","doi-asserted-by":"crossref","first-page":"1243","DOI":"10.1016\/j.tcs.2010.12.049","volume":"412","author":"H. Attiya","year":"2011","unstructured":"Attiya, H., Hillel, E.: Highly concurrent multi-word synchronization. Theor. Comput. Sci. 412(12\u201314), 1243\u20131262 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9420_CR6","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H. Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, New York (2004)","edition":"2"},{"key":"9420_CR7","first-page":"261","volume-title":"Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"G. Barnes","year":"1993","unstructured":"Barnes, G.: A method for implementing lock-free shared-data structures. In: Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp.\u00a0261\u2013270 (1993)"},{"key":"9420_CR8","first-page":"59","volume-title":"Proceedings of the 14th International Conference on Distributed Computing (DISC)","author":"D. Detlefs","year":"2000","unstructured":"Detlefs, D., Flood, C.H., Garthwaite, A., Martin, P., Shavit, N., Steele, G.L. Jr.: Even better DCAS-based concurrent deques. In: Proceedings of the 14th International Conference on Distributed Computing (DISC), pp.\u00a059\u201373 (2000)"},{"key":"9420_CR9","first-page":"216","volume-title":"Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"S. Doherty","year":"2004","unstructured":"Doherty, S., Detlefs, D.L., Groves, L., Flood, C.H., Luchangco, V., Martin, P.A., Moir, M., Shavit, N., Steele, G.L. Jr.: DCAS is not a silver bullet for nonblocking algorithm design. In: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp.\u00a0216\u2013224 (2004)"},{"key":"9420_CR10","first-page":"493","volume-title":"Proceedings of the 19th International Symposium on Distributed Computing (DISC)","author":"F.E. Fich","year":"2005","unstructured":"Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free step complexity: Lock-free DCAS as an example. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp.\u00a0493\u2013494 (2005)"},{"key":"9420_CR11","unstructured":"Greenwald, M.: Non-blocking synchronization and system design. PhD thesis, Stanford University, August 1999"},{"key":"9420_CR12","first-page":"260","volume-title":"Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC)","author":"M. Greenwald","year":"2002","unstructured":"Greenwald, M.: Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS. In: Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC), pp.\u00a0260\u2013269 (2002)"},{"key":"9420_CR13","first-page":"249","volume-title":"Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"P.H. Ha","year":"2005","unstructured":"Ha, P.H., Tsigas, P., Wattenhofer, M., Wattenhofer, R.: Efficient multi-word locking using randomization. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a0249\u2013257 (2005)"},{"key":"9420_CR14","first-page":"300","volume-title":"Proceedings of the 15th International Conference on Distributed Computing (DISC)","author":"T.L. Harris","year":"2001","unstructured":"Harris, T.L.: A pragmatic implementation of non-blocking linked-lists. In: Proceedings of the 15th International Conference on Distributed Computing (DISC), pp.\u00a0300\u2013314 (2001)"},{"key":"9420_CR15","first-page":"388","volume-title":"Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA)","author":"T.L. Harris","year":"2003","unstructured":"Harris, T.L., Fraser, K.: Language support for lightweight transactions. In: Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pp.\u00a0388\u2013402 (2003)"},{"issue":"3","key":"9420_CR16","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M. Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9420_CR17","first-page":"522","volume-title":"Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS)","author":"M. Herlihy","year":"2003","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 (ICDCS), pp.\u00a0522\u2013529 (2003)"},{"key":"9420_CR18","unstructured":"IBM. IBM System\/370 Extended Architecture, Principle of Operation. IBM Publication No. SA22-7085 (1983)"},{"key":"9420_CR19","unstructured":"Merritt, R.: IBM plants transactional memory in CPU. EETimes, August 2011. http:\/\/www.eetimes.com\/electronics-news\/4218914\/IBM-plants-transactional-memory-in-CPU"},{"key":"9420_CR20","first-page":"73","volume-title":"Proceedings of the 14th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"M.M. Michael","year":"2002","unstructured":"Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In: Proceedings of the 14th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp.\u00a073\u201382 (2002)"},{"key":"9420_CR21","first-page":"651","volume-title":"Proceedings of the 9th Euro-Par Conference on Parallel Processing","author":"M.M. Michael","year":"2003","unstructured":"Michael, M.M.: CAS-based lock-free algorithm for shared deques. In: Proceedings of the 9th Euro-Par Conference on Parallel Processing, pp.\u00a0651\u2013660 (2003)"},{"key":"9420_CR22","unstructured":"Reinders, J.: Transactional synchronization in Haswell, February 2012. http:\/\/software.intel.com\/en-us\/blogs\/2012\/02\/07\/transactional-synchronization-in-haswell\/"},{"key":"9420_CR23","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/978-3-642-10631-6_46","volume-title":"Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC)","author":"J. Schneider","year":"2009","unstructured":"Schneider, J., Wattenhofer, R.: Bounds on contention management algorithms. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pp.\u00a0441\u2013451 (2009)"},{"issue":"2","key":"9420_CR24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s004460050028","volume":"10","author":"N. Shavit","year":"1997","unstructured":"Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput. 10(2), 99\u2013116 (1997)","journal-title":"Distrib. Comput."},{"key":"9420_CR25","unstructured":"Sundell, H.: Efficient and practical non-blocking data structures. PhD thesis, Chalmers University of Technology (2004)"},{"issue":"7","key":"9420_CR26","doi-asserted-by":"crossref","first-page":"1008","DOI":"10.1016\/j.jpdc.2008.03.001","volume":"68","author":"H. Sundell","year":"2008","unstructured":"Sundell, H., Tsigas, P.: Lock-free deques and doubly linked lists. J. Parallel Distrib. Comput. 68(7), 1008\u20131020 (2008)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9420_CR27","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1145\/137097.137873","volume-title":"Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS)","author":"J. Turek","year":"1992","unstructured":"Turek, J., Shasha, D., Prakash, S.: Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp.\u00a0212\u2013222 (1992)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9420-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9420-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9420-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T09:42:32Z","timestamp":1743932552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9420-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,1]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9420"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9420-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2012,8,1]]}}}