{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:44:57Z","timestamp":1749825897029,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["CCF-1217921","CCF-1301926"],"award-info":[{"award-number":["CCF-1217921","CCF-1301926"]}]},{"name":"National Science Foundation","award":["IIS-1447786"],"award-info":[{"award-number":["IIS-1447786"]}]},{"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"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Postgraduate Scholarship"],"award-info":[{"award-number":["Postgraduate Scholarship"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["ER26116\/DE-SC0008923"],"award-info":[{"award-number":["ER26116\/DE-SC0008923"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Faculty of Arts and Sciences, University of Toronto","award":["Postdoctoral Fellowship"],"award-info":[{"award-number":["Postdoctoral Fellowship"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00446-019-00361-3","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T14:57:57Z","timestamp":1568041077000},"page":"125-144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A complexity-based classification for multiprocessor synchronization"],"prefix":"10.1007","volume":"33","author":[{"given":"Faith","family":"Ellen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6151-1061","authenticated-orcid":false,"given":"Rati","family":"Gelashvili","sequence":"additional","affiliation":[]},{"given":"Nir","family":"Shavit","sequence":"additional","affiliation":[]},{"given":"Leqi","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,4]]},"reference":[{"issue":"4","key":"361_CR1","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y Afek","year":"1993","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873\u2013890 (1993)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Aspnes, J., Attiya, H., Censor-Hillel, K.: Polylogarithmic concurrent data structures from monotone circuits. J. ACM 59(1), 2:1\u20132:24 (2012)","key":"361_CR2","DOI":"10.1145\/2108242.2108244"},{"issue":"3","key":"361_CR3","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00224-013-9448-1","volume":"55","author":"J Aspnes","year":"2014","unstructured":"Aspnes, J., Ellen, F.: Tight bounds for adopt-commit objects. Theory Comput. Syst. 55(3), 451\u2013474 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"361_CR4","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0196-6774(90)90021-6","volume":"11","author":"J Aspnes","year":"1990","unstructured":"Aspnes, J., Herlihy, M.: Fast randomized consensus using shared memory. J. Algorithms 11(3), 441\u2013461 (1990)","journal-title":"J. Algorithms"},{"key":"361_CR5","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations, and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.L.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd edn. Wiley, Hoboken (2004)","edition":"2"},{"issue":"2","key":"361_CR6","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s00446-017-0301-7","volume":"31","author":"Z Bouzid","year":"2018","unstructured":"Bouzid, Z., Raynal, M., Sutra, P.: Anonymous obstruction-free $$(n, k)$$-set agreement with $$n-k+1$$ atomic read\/write registers. Distrib. Comput. 31(2), 99\u2013117 (2018)","journal-title":"Distrib. Comput."},{"unstructured":"Bowman, J.R.: Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k. Technical report TR2011-681, Computer Science Department, Dartmouth College (2011). \nhttp:\/\/www.cs.dartmouth.edu\/reports\/TR2011-681.pdf","key":"361_CR7"},{"unstructured":"David, M.: Wait-free linearizable queue implementations. Master\u2019s thesis, University of Toronto (2004)","key":"361_CR8"},{"doi-asserted-by":"crossref","unstructured":"David, M., Brodsky, A., Fich, F.E.: Restricted stack implementations. In: Proceedings of the 19th International Conference on Distributed Computing, (DISC), pp. 137\u2013151 (2005)","key":"361_CR9","DOI":"10.1007\/11561927_12"},{"doi-asserted-by":"crossref","unstructured":"Ellen, F., Gelashvili, R., Shavit, N., Zhu, L.: A complexity-based hierarchy for multiprocessor synchronization:[Extended Abstract]. In: Proceedings of the 35th ACM Symposium on Principles of Distributed Computing, (PODC), pp. 289\u2013298 (2016)","key":"361_CR10","DOI":"10.1145\/2933057.2933113"},{"unstructured":"Ellen, F., Gelashvili, R., Zhu, L.: Revisionist simulations: a new approach to proving space lower bounds. In: Proceedings of the 37th ACM Symposium on Principles of Distributed Computing, (PODC), pp. 61\u201370, (2018)","key":"361_CR11"},{"issue":"5","key":"361_CR12","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"F Fich","year":"1998","unstructured":"Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. ACM 45(5), 843\u2013862 (1998)","journal-title":"J. ACM"},{"unstructured":"Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proceedings of the 19th International Conference on Distributed Computing, (DISC), pp. 78\u201392, (2005)","key":"361_CR13"},{"issue":"4","key":"361_CR14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00446-018-0331-9","volume":"31","author":"R Gelashvili","year":"2018","unstructured":"Gelashvili, R.: On the optimal space complexity of consensus for anonymous processes. Distrib. Comput. 31(4), 317\u2013326 (2018)","journal-title":"Distrib. Comput."},{"unstructured":"Gelashvili, R., Keidar, I., Spiegelman, A., Wattenhofer, R.: Brief announcement: Towards reduced instruction sets for synchronization. In: Proceedings of the 31st International Conference on Distributed Computing, (DISC), pp. 53:1\u201353:4 (2017)","key":"361_CR15"},{"doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: An $$\\cal{O}(\\sqrt{n})$$ space bound for obstruction-free leader election. In: Proceedings of the 27th International Symposium on Distributed Computing, (DISC), pp. 46\u201360 (2013)","key":"361_CR16","DOI":"10.1007\/978-3-642-41527-2_4"},{"issue":"3","key":"361_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00446-007-0042-0","volume":"20","author":"R Guerraoui","year":"2007","unstructured":"Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3), 165\u2013177 (2007)","journal-title":"Distrib. Comput."},{"issue":"1","key":"361_CR18","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 Trans. Program. Lang. Syst. (TOPLAS) 13(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"unstructured":"Herlihy, M., Ruppert, E.: On the existence of booster types. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pp. 653\u2013663, (2000)","key":"361_CR19"},{"key":"361_CR20","volume-title":"The Art of Multiprocessor Programming","author":"M Herlihy","year":"2012","unstructured":"Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Elsevier, Amsterdam (2012)"},{"unstructured":"Intel: Transactional Synchronization in Haswell, (2012). \nhttp:\/\/software.intel.com\/en-us\/blogs\/2012\/02\/07\/transactional-synchronization-in-haswell","key":"361_CR21"},{"doi-asserted-by":"crossref","unstructured":"Jayanti, P.: Robust wait-free hierarchies. J. ACM 44(4), 592\u2013614 (1997)","key":"361_CR22","DOI":"10.1145\/263867.263888"},{"issue":"2","key":"361_CR23","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1137\/S0097539797317299","volume":"30","author":"P Jayanti","year":"2000","unstructured":"Jayanti, P., Tan, K., Toueg, S.: Time and space lower bounds for nonblocking implementations. SIAM J. Comput. 30(2), 438\u2013456 (2000)","journal-title":"SIAM J. Comput."},{"unstructured":"Khanchandani, P., Wattenhofer, R.: On the importance of synchronization primitives with low consensus numbers. In: Proceedings of the 19th International Conference on Distributed Computing and Networking, (ICDCN), pp. 18:1\u201318:10, (2018)","key":"361_CR24"},{"issue":"3","key":"361_CR25","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1137\/S0097539798335766","volume":"30","author":"W-K Lo","year":"2000","unstructured":"Lo, W.-K., Hadzilacos, V.: All of us are smarter than any of us: nondeterministic wait-free hierarchies are not robust. SIAM J. Comput. 30(3), 689\u2013728 (2000)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Perrin, M.: Sp\u00e9cification des objets partag\u00e9s dans le syst\u00e8mes r\u00e9partis sans attente (specification of shared objects in wait-free distributed systems). Ph.D. thesis, University of Nantes, France (2016)","key":"361_CR26","DOI":"10.1016\/B978-1-78548-226-7.50001-X"},{"unstructured":"Perrin, M., Most\u00e9faoui, A., Jard, C.: Causal consistency: beyond memory. In: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (PPOPP), pp. 26:1\u201326:12, (2016)","key":"361_CR27"},{"key":"361_CR28","volume-title":"Concurrent Programming: Algorithms, Principles, and Foundations","author":"M Raynal","year":"2012","unstructured":"Raynal, M.: Concurrent Programming: Algorithms, Principles, and Foundations. Springer, Berlin (2012)"},{"issue":"4","key":"361_CR29","doi-asserted-by":"publisher","first-page":"1156","DOI":"10.1137\/S0097539797329439","volume":"30","author":"E Ruppert","year":"2000","unstructured":"Ruppert, E.: Determining consensus numbers. SIAM J. Comput. 30(4), 1156\u20131168 (2000)","journal-title":"SIAM J. Comput."},{"unstructured":"Schenk, E.: The consensus hierarchy is not robust. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, (PODC), pp. 279, (1997)","key":"361_CR30"},{"key":"361_CR31","volume-title":"Synchronization Algorithms and Concurrent Programming","author":"G Taubenfeld","year":"2006","unstructured":"Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Education, London (2006)"},{"unstructured":"Zhu, L.: Brief announcement: tight space bounds for memoryless anonymous consensus. In: Proceedings of the 29th International Conference on Distributed Computing, (DISC), pp. 665, (2015)","key":"361_CR32"},{"unstructured":"Zhu, L.: A tight space bound for consensus. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing, (STOC), pp. 345\u2013350, (2016)","key":"361_CR33"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00361-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-019-00361-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00361-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T23:20:03Z","timestamp":1599088803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-019-00361-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,4]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["361"],"URL":"https:\/\/doi.org\/10.1007\/s00446-019-00361-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2019,9,4]]},"assertion":[{"value":"4 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}