{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:11Z","timestamp":1767339971393},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T00:00:00Z","timestamp":1378857600000},"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":[[2014,10]]},"DOI":"10.1007\/s00224-013-9491-y","type":"journal-article","created":{"date-parts":[[2013,9,10]],"date-time":"2013-09-10T05:57:31Z","timestamp":1378792651000},"page":"475-520","source":"Crossref","is-referenced-by-count":26,"title":["Highly-Efficient Wait-Free Synchronization"],"prefix":"10.1007","volume":"55","author":[{"given":"Panagiota","family":"Fatourou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaos D.","family":"Kallimanis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,11]]},"reference":[{"key":"9491_CR1","first-page":"538","volume-title":"Proceedings of the 27th ACM Symposium on Theory of Computing","author":"Y. Afek","year":"1995","unstructured":"Afek, Y., Dauber, D., Touitou, D.: Wait-free made fast. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 538\u2013547 (1995)"},{"key":"9491_CR2","first-page":"262","volume-title":"Proceedings of the 40th Symposium on Foundations of Computer Science","author":"Y. Afek","year":"1999","unstructured":"Afek, Y., Stupp, G., Touitou, D.: Long-lived adaptive collect with applications. In: Proceedings of the 40th Symposium on Foundations of Computer Science, pp. 262\u2013272 (1999)"},{"key":"9491_CR3","first-page":"483","volume-title":"Proceedings of National Computer Conference of the American Federation of Information Processing Societies","author":"G. Amdahl","year":"1967","unstructured":"Amdahl, G.: Validity of the single processor approach to achieving large-scale computing capabilities. In: Proceedings of National Computer Conference of the American Federation of Information Processing Societies, pp. 483\u2013485 (1967)"},{"key":"9491_CR4","first-page":"184","volume-title":"Proceedings of the 14th ACM Symposium on Principles of Distributed Computing","author":"J.H. Anderson","year":"1995","unstructured":"Anderson, J.H., Moir, M.: Universal constructions for multi-object operations. In: Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pp. 184\u2013193 (1995)"},{"issue":"12","key":"9491_CR5","doi-asserted-by":"crossref","first-page":"1317","DOI":"10.1109\/71.819952","volume":"10","author":"J.H. Anderson","year":"1999","unstructured":"Anderson, J.H., Moir, M.: Universal constructions for large objects. IEEE Trans. Parallel Distrib. Syst. 10(12), 1317\u20131332 (1999)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9491_CR6","first-page":"336","volume-title":"Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"H. Attiya","year":"2008","unstructured":"Attiya, H., Guerraoui, R., Ruppert, E.: Partial snapshot objects. In: Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 336\u2013343 (2008)"},{"key":"9491_CR7","first-page":"261","volume-title":"Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures","author":"G. Barnes","year":"1993","unstructured":"Barnes, G.: A method for implementing lock-free shared data structures. In: Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 261\u2013270 (1993)"},{"key":"9491_CR8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1145\/378993.379232","volume-title":"Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems","author":"E.D. Berger","year":"2000","unstructured":"Berger, E.D., McKinley, K.S., Blumofe, R.D., Wilson, P.R.: Hoard: a scalable memory allocator for multithreaded applications. In: Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 117\u2013128 (2000)"},{"key":"9491_CR9","first-page":"335","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures","author":"P. Chuong","year":"2010","unstructured":"Chuong, P., Ellen, F., Ramachandran, V.: A universal construction for wait-free transaction friendly data structures. In: Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 335\u2013344 (2010)"},{"key":"9491_CR10","doi-asserted-by":"crossref","unstructured":"Conway, P., Kalyanasundharam, N., Donley, G., Lepak, K., Hughes, B.: Blade Computing with the AMD Opteron Processor (Magny-Cours). Hot chips 21 (2009)","DOI":"10.1109\/HOTCHIPS.2009.7478349"},{"key":"9491_CR11","unstructured":"Craig, T.S.: Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02, Department of Computer Science, University of Washington (1993)"},{"key":"9491_CR12","first-page":"127","volume-title":"Proceedings of the 23rd International Symposium on Distributed Computing","author":"P. Fatourou","year":"2009","unstructured":"Fatourou, P., Kallimanis, N.D.: The RedBlue adaptive universal constructions. In: Proceedings of the 23rd International Symposium on Distributed Computing, pp. 127\u2013141 (2009)"},{"key":"9491_CR13","unstructured":"Fatourou, P., Kallimanis, N.D.: Fast Implementations of Shared Objects using Fetch&Add. Tech. Rep. TR 02-2010, Department of Computer Science, University of Ioannina (2010)"},{"key":"9491_CR14","doi-asserted-by":"crossref","unstructured":"Fatourou, P., Kallimanis, N.D.: A Highly-Efficient Wait-Free Universal Construction. Tech. Rep. TR 01-2011, Department of Computer Science, University of Ioannina (2011)","DOI":"10.1145\/1989493.1989549"},{"key":"9491_CR15","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1145\/2145816.2145849","volume-title":"Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","author":"P. Fatourou","year":"2012","unstructured":"Fatourou, P., Kallimanis, N.D.: Revisiting the combining synchronization technique. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp.\u00a0257\u2013266. ACM, New York (2012)"},{"key":"9491_CR16","unstructured":"Hendler, D., Incze, I., Shavit, N., Tzafrir, M.: The source code for flat-combining. http:\/\/github.com\/mit-carbon\/Flat-Combining"},{"key":"9491_CR17","first-page":"355","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures","author":"D. Hendler","year":"2010","unstructured":"Hendler, D., Incze, I., Shavit, N., Tzafrir, M.: Flat combining and the synchronization-parallelism tradeoff. In: Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 355\u2013364 (2010)"},{"key":"9491_CR18","first-page":"206","volume-title":"Proceedings of the 16th ACM Symposium on Parallel Algorithms and Architectures","author":"D. Hendler","year":"2004","unstructured":"Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free stack algorithm. In: Proceedings of the 16th ACM Symposium on Parallel Algorithms and Architectures, pp. 206\u2013215 (2004)"},{"key":"9491_CR19","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13, 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"5","key":"9491_CR20","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1145\/161468.161469","volume":"15","author":"M. Herlihy","year":"1993","unstructured":"Herlihy, M.: A methodology for implementing highly concurrent data objects. ACM Trans. Program. Lang. Syst. 15(5), 745\u2013770 (1993)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"0","key":"9491_CR21","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/S1571-0661(04)81017-X","volume":"78","author":"M. Herlihy","year":"2003","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Space- and time-adaptive nonblocking algorithms. Electron. Notes Theor. Comput. Sci. 78(0), 260\u2013280 (2003)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"3","key":"9491_CR22","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":"9491_CR23","first-page":"142","volume-title":"Proceedings of the 23rd International Symposium on Distributed Computing","author":"D. Imbs","year":"2009","unstructured":"Imbs, D., Raynal, M.: Help when needed, but no more: efficient Read\/Write partial snapshot. In: Proceedings of the 23rd International Symposium on Distributed Computing, pp. 142\u2013156 (2009)"},{"key":"9491_CR24","first-page":"201","volume-title":"Proceedings of the 17th ACM Symposium on Principles of Distributed Computing","author":"P. Jayanti","year":"1998","unstructured":"Jayanti, P.: A time complexity lower bound for randomized implementations of some shared objects. In: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, pp. 201\u2013210 (1998)"},{"key":"9491_CR25","unstructured":"Kallimanis, N.D., Fatourou, P.: The source code for PSim. http:\/\/code.google.com\/p\/sim-universal-construction"},{"key":"9491_CR26","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/IPPS.1994.288305","volume-title":"Proceedings of the 8th International Parallel Processing Symposium","author":"P.S. Magnusson","year":"1994","unstructured":"Magnusson, P.S., Landin, A., Hagersten, E.: Queue locks on cache coherent multiprocessors. In: Proceedings of the 8th International Parallel Processing Symposium, pp. 165\u2013171 (1994)"},{"issue":"1","key":"9491_CR27","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/103727.103729","volume":"9","author":"J.M. Mellor-Crummey","year":"1991","unstructured":"Mellor-Crummey, J.M., Scott, M.L.: Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9(1), 21\u201365 (1991)","journal-title":"ACM Trans. Comput. Syst."},{"key":"9491_CR28","first-page":"267","volume-title":"Proceedings of the 15th ACM Symposium on Principles of Distributed Computing","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 ACM Symposium on Principles of Distributed Computing, pp. 267\u2013275 (1996)"},{"key":"9491_CR29","first-page":"182","volume-title":"Proceedings of International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications","author":"Y. Oyama","year":"1999","unstructured":"Oyama, Y., Taura, K., Yonezawa, A.: Executing parallel programs with synchronization bottlenecks efficiently. In: Proceedings of International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications, pp. 182\u2013204 (1999)"},{"key":"9491_CR30","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1145\/1217935.1217965","volume-title":"Proceedings of the 1st ACM SIGOPS\/EuroSys European Conference on Computer Systems 2006, EuroSys \u201906","author":"O. Shalev","year":"2006","unstructured":"Shalev, O., Shavit, N.: Predictive log-synchronization. In: Proceedings of the 1st ACM SIGOPS\/EuroSys European Conference on Computer Systems 2006, EuroSys \u201906, pp. 305\u2013315 (2006)"},{"issue":"11","key":"9491_CR31","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1006\/jpdc.2000.1621","volume":"60","author":"N. Shavit","year":"2000","unstructured":"Shavit, N., Zemach, A.: Combining funnels: a dynamic approach to software combining. J. Parallel Distrib. Comput. 60(11), 1355\u20131387 (2000)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9491_CR32","volume-title":"Synchronization Algorithms and Concurrent Programming","author":"G. Taubenfeld","year":"2006","unstructured":"Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Prentice Hall, New York (2006)"},{"key":"9491_CR33","unstructured":"Treiber, R.K.: Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, (1986)"},{"issue":"4","key":"9491_CR34","first-page":"388","volume":"100","author":"P.C. Yew","year":"1987","unstructured":"Yew, P.C., Tzeng, N.F., Lawrie, D.H.: Distributing hot-spot addressing in large-scale multiprocessors. IEEE Trans. Comput. 100(4), 388\u2013395 (1987)","journal-title":"IEEE Trans. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9491-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9491-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9491-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T23:15:28Z","timestamp":1646522128000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9491-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,11]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["9491"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9491-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,11]]}}}