{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:46Z","timestamp":1750308826119,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["953\/061344\/06"],"award-info":[{"award-number":["953\/061344\/06"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>\n            <jats:italic>Obstruction-free<\/jats:italic>\n            implementations of concurrent objects are optimized for the common case where there is no\n            <jats:italic>step contention<\/jats:italic>\n            , and were recently advocated as a solution to the costs associated with synchronization without locks. In this article, we study this claim and this goes through precisely defining the notions of obstruction-freedom and step contention. We consider several classes of obstruction-free implementations, present corresponding generic object implementations, and prove lower bounds on their complexity. Viewed collectively, our results establish that the worst-case operation time complexity of obstruction-free implementations is high, even in the absence of step contention. We also show that lock-based implementations are not subject to some of the time-complexity lower bounds we present.\n          <\/jats:p>","DOI":"10.1145\/1538902.1538908","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:17Z","timestamp":1246367417000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["The complexity of obstruction-free implementations"],"prefix":"10.1145","volume":"56","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hendler","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Kuznetsov","sequence":"additional","affiliation":[{"name":"TU Berlin\/Deutsche Telekom Laboratories, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, 262--272","author":"Afek Y.","key":"e_1_2_1_1_1","unstructured":"Afek , Y. , Stupp , G. , and Touitou , D . 1999. Long-lived adaptive collect with applications . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, 262--272 . Afek, Y., Stupp, G., and Touitou, D. 1999. Long-lived adaptive collect with applications. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, 262--272."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460100060"},{"key":"e_1_2_1_3_1","volume-title":"Tech. Rep. HPL-2003-241, HP Laboratories Palo Alto.","author":"Aguilera M. K.","year":"2003","unstructured":"Aguilera , M. K. , and Fr\u00e8lund , S . 2003 . Strict linearizability and the power of aborting. Tech. Rep. HPL-2003-241, HP Laboratories Palo Alto. Aguilera, M. K., and Fr\u00e8lund, S. 2003. Strict linearizability and the power of aborting. Tech. Rep. HPL-2003-241, HP Laboratories Palo Alto."},{"volume-title":"Proceedings of the 20th International Symposium on Distributed Computing (DISC). Springer-Verlag, Berlin \/Heidelberg, Germany, 534--536","author":"Aguilera M. K.","key":"e_1_2_1_4_1","unstructured":"Aguilera , M. K. , Frolund , S. , Hadzilacos , V. , Horn , S. L. , and Toueg , S . 2006. Abortable shared objects . In Proceedings of the 20th International Symposium on Distributed Computing (DISC). Springer-Verlag, Berlin \/Heidelberg, Germany, 534--536 . Aguilera, M. K., Frolund, S., Hadzilacos, V., Horn, S. L., and Toueg, S. 2006. Abortable shared objects. In Proceedings of the 20th International Symposium on Distributed Computing (DISC). Springer-Verlag, Berlin \/Heidelberg, Germany, 534--536."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90021-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792541"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/637437.637447"},{"volume-title":"The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls","author":"Dijkstra E. W.","key":"e_1_2_1_9_1","unstructured":"Dijkstra , E. W. 2002. Cooperating sequential processes . In The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls . Springer-Verlag , New York , 65--138. Dijkstra, E. W. 2002. Cooperating sequential processes. In The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls. Springer-Verlag, New York, 65--138."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/268999.269000"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290183"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.47"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384008"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0051-z"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"volume-title":"Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, Los Alamitos, 522--529","author":"Herlihy M.","key":"e_1_2_1_17_1","unstructured":"Herlihy , M. , Luchangco , V. , and Moir , M . 2003a. Obstruction-free synchronization: Double-ended queues as an example . In Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, Los Alamitos, 522--529 . Herlihy, M., Luchangco, V., and Moir, M. 2003a. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, Los Alamitos, 522--529."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872048"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317299"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_22_1","volume-title":"Concurrent Programming in Java(TM): Design Principles and Patterns","author":"Lea D.","unstructured":"Lea , D. 1999. Concurrent Programming in Java(TM): Design Principles and Patterns , 2 nd ed. Addison-Wesley , Reading . Lea, D. 1999. Concurrent Programming in Java(TM): Design Principles and Patterns, 2nd ed. Addison-Wesley, Reading.","edition":"2"},{"volume-title":"Memory Requirements for Agreement Among Unreliable Asynchronous Processes","author":"Loui M. C.","key":"e_1_2_1_23_1","unstructured":"Loui , M. C. , and Abu-Amara , H. H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes . JAI Press , Greenwich , 163--183. Loui, M. C., and Abu-Amara, H. H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes. JAI Press, Greenwich, 163--183."},{"volume-title":"Proceedings of the 17th International Symposium on Distributed Computing (DISC). Springer-Verlag, Berlin\/Heidelberg, Germany, 45--59","author":"Luchangco V.","key":"e_1_2_1_24_1","unstructured":"Luchangco , V. , Moir , M. , and Shavit , N . 2003. On the uncontended complexity of consensus . In Proceedings of the 17th International Symposium on Distributed Computing (DISC). Springer-Verlag, Berlin\/Heidelberg, Germany, 45--59 . Luchangco, V., Moir, M., and Shavit, N. 2003. On the uncontended complexity of consensus. In Proceedings of the 17th International Symposium on Distributed Computing (DISC). Springer-Verlag, Berlin\/Heidelberg, Germany, 45--59."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803398"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277755"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1538902.1538908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:53Z","timestamp":1750278413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1538902.1538908"],"URL":"https:\/\/doi.org\/10.1145\/1538902.1538908","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2007-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}