{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:01Z","timestamp":1740109381452,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T00:00:00Z","timestamp":1720742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T00:00:00Z","timestamp":1720742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1749\/14, 380\/18"],"award-info":[{"award-number":["1749\/14, 380\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ono Academic College Research Fund"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s00224-024-10184-w","type":"journal-article","created":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T08:02:19Z","timestamp":1720771339000},"page":"1372-1426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds on the Amortized Time Complexity of Shared Objects"],"prefix":"10.1007","volume":"68","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[]},{"given":"Arie","family":"Fouren","sequence":"additional","affiliation":[]},{"given":"Jeremy","family":"Ko","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,12]]},"reference":[{"issue":"2","key":"10184_CR1","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00446-003-0088-6","volume":"16","author":"JH Anderson","year":"2003","unstructured":"Anderson, J.H., Kim, Y.-J., Herman, T.: Shared-memory mutual exclusion: major research trends since 1986. Distrib. Comput. 16(2), 75\u2013110 (2003)","journal-title":"Distrib. Comput."},{"key":"10184_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, J.H., Moir, M.: Universal constructions for multi-object operations. In Proceedings of the 14th annual ACM symposium on Principles of Distributed Computing, pp. 184\u2013193, (1995)","DOI":"10.1145\/224964.224985"},{"key":"10184_CR3","doi-asserted-by":"crossref","unstructured":"Anderson, R.J., Woll, H.: Wait-free parallel algorithms for the union-find problem. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC \u201991, pp. 370\u2013380, (1991)","DOI":"10.1145\/103418.103458"},{"key":"10184_CR4","unstructured":"Asbell, S.M., Ruppert, E.: A wait-free deque with polylogarithmic step complexity. In 27th International Conference on Principles of Distributed Systems, OPODIS 2023, vol. 286, pp. 17:1\u201317:22, (2023)"},{"key":"10184_CR5","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.jpdc.2017.05.010","volume":"109","author":"H Attiya","year":"2017","unstructured":"Attiya, H., Fouren, A.: Poly-logarithmic adaptive algorithms require revealing primitives. J. Parallel Distrib. Comput. 109, 102\u2013116 (2017)","journal-title":"J. Parallel Distrib. Comput."},{"key":"10184_CR6","unstructured":"Attiya, H., Fouren, A.: Lower bounds on the amortized time complexity of shared objects. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2018)"},{"issue":"1","key":"10184_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00263762","volume":"9","author":"R Bayer","year":"1977","unstructured":"Bayer, R., Schkolnick, M.: Concurrency of operations on B-trees. Acta Informatica 9(1), 1\u201321 (1977)","journal-title":"Acta Informatica"},{"key":"10184_CR8","unstructured":"Blelloch, G.E. Wei, Y.: LL\/SC and atomic copy: Constant time, space efficient implementations using only pointer-width CAS. In 34th International Symposium on Distributed Computing, DISC 2020, pp. 5:1\u20135:17, (2020)"},{"key":"10184_CR9","doi-asserted-by":"crossref","unstructured":"Ellen, F., Fatourou, P., Helga, J., Ruppert, E.: The amortized complexity of non-blocking binary search trees. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC \u201914, pp. 332\u2013340, (2014)","DOI":"10.1145\/2611462.2611486"},{"key":"10184_CR10","doi-asserted-by":"crossref","unstructured":"Fich, F., Hendler, D., Shavit, N.: On the inherent weakness of conditional synchronization primitives. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, PODC \u201904, pp. 80\u201387, (2004)","DOI":"10.1145\/1011767.1011780"},{"key":"10184_CR11","doi-asserted-by":"crossref","unstructured":"Fomitchev, M., Ruppert, E.: Lock-free linked lists and skip lists. In Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, PODC \u201904, pp. 50\u201359, (2004)","DOI":"10.1145\/1011767.1011776"},{"key":"10184_CR12","doi-asserted-by":"crossref","unstructured":"Harris, T.: A pragmatic implementation of non-blocking linked-lists. Distrib. Comput. 300\u2013314, (2001)","DOI":"10.1007\/3-540-45414-4_21"},{"key":"10184_CR13","doi-asserted-by":"crossref","unstructured":"Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer, W.N., Shavit, N.: A lazy concurrent list-based set algorithm. In Proceedings of the 9th international conference on Principles of Distributed Systems, pp. 3\u201316. Springer-Verlag, (2005)","DOI":"10.1007\/11795490_3"},{"key":"10184_CR14","unstructured":"Herlihy, M., Shavit, N.: The art of multiprocessor programming. Morgan Kaufmann, (2011)"},{"key":"10184_CR15","doi-asserted-by":"crossref","unstructured":"Jayanti, P., Petrovic, S.: Efficient and practical constructions of LL\/SC variables. In Proceedings of the 22nd annual symposium on Principles of Distributed Computing, pp. 285\u2013294, (2003)","DOI":"10.1145\/872035.872078"},{"issue":"6","key":"10184_CR16","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s00446-020-00388-x","volume":"34","author":"SV Jayanti","year":"2021","unstructured":"Jayanti, S.V., Tarjan, R.E.: Concurrent disjoint set union. Distrib. Comput. 34(6), 413\u2013436 (2021)","journal-title":"Distrib. Comput."},{"issue":"6","key":"10184_CR17","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s00446-011-0152-6","volume":"24","author":"Y-J Kim","year":"2012","unstructured":"Kim, Y.-J., Anderson, J.H.: A time complexity lower bound for adaptive mutual exclusion. Distrib. Comput. 24(6), 271\u2013297 (2012)","journal-title":"Distrib. Comput."},{"key":"10184_CR18","doi-asserted-by":"crossref","unstructured":"Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the 14th annual ACM symposium on Parallel Algorithms and Architectures, pp. 73\u201382. ACM, (2002)","DOI":"10.1145\/564870.564881"},{"key":"10184_CR19","doi-asserted-by":"crossref","unstructured":"Michael, M.M.: Practical lock-free and wait-free LL\/SC\/VL implementations using 64-bit CAS. In 18th International Conference on Distributed Computing, DISC 2004, pp. 144\u2013158. Springer, (2004)","DOI":"10.1007\/978-3-540-30186-8_11"},{"key":"10184_CR20","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":"10184_CR21","doi-asserted-by":"crossref","unstructured":"Naderibeni, H., Ruppert E.: A wait-free queue with polylogarithmic step complexity. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, pp. 124\u2013134, (2023)","DOI":"10.1145\/3583668.3594565"},{"key":"10184_CR22","unstructured":"Ruppert, E.: Analysing the average time complexity of lock-free data structures. In Workshop on Complexity and Analysis of Distributed Algorithms, (2016). http:\/\/www.birs.ca\/events\/2016\/5-day-workshops\/16w5152\/videos\/watch\/201612011630-Ruppert.html Accessed 22-Mar-2017"},{"key":"10184_CR23","unstructured":"Shafiei, N.: Non-blocking data structures handling multiple changes atomically. PhD thesis, York University, (2015)"},{"key":"10184_CR24","volume-title":"Systems programming: coping with parallelism","author":"RK Treiber","year":"1986","unstructured":"Treiber, R.K.: Systems programming: coping with parallelism. Thomas J Watson Research Center, International Business Machines Incorporated (1986)"},{"key":"10184_CR25","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"},{"key":"10184_CR26","doi-asserted-by":"crossref","unstructured":"Valois, J.D.: Lock-free linked lists using compare-and-swap. In Proceedings of the 14th annual ACM symposium on Principles of Distributed Computing, pp. 214\u2013222. ACM, (1995)","DOI":"10.1145\/224964.224988"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10184-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10184-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10184-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:54:22Z","timestamp":1729850062000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10184-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,12]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10184"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10184-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,7,12]]},"assertion":[{"value":"20 June 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}