{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T04:03:24Z","timestamp":1748059404146,"version":"3.41.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ANR-DUCAT","award":["-20-EC48-0006","-20-EC48-0006","-20-EC48-0006"],"award-info":[{"award-number":["-20-EC48-0006","-20-EC48-0006","-20-EC48-0006"]}]},{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","award":["3684 under second call for research projects to support faculty members"],"award-info":[{"award-number":["3684 under second call for research projects to support faculty members"]}],"id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"name":"IDEX-Universit\u00e9 Paris Cit\u00e9"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00446-025-00476-w","type":"journal-article","created":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T06:38:58Z","timestamp":1738910338000},"page":"73-94","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["When is recoverable consensus harder than consensus?"],"prefix":"10.1007","volume":"38","author":[{"given":"Carole","family":"Delporte-Gallet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiota","family":"Fatourou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugues","family":"Fauconnier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Ruppert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"476_CR1","unstructured":"Aguilera, M.K., Fr\u00f8lund, S.: Strict linearizability and the power of aborting. Technical Report HPL-2003-241, HP Laboratories Palo Alto, 2003. Available from https:\/\/www.hpl.hp.com\/techreports\/2003\/HPL-2003-241.html"},{"key":"476_CR2","doi-asserted-by":"crossref","unstructured":"Attiya, H., Ben-Baruch, O., Fatourou, P., Hendler, D., Kosmas, E.: Detectable recovery of lock-free data structures. In: Proceedings of the 27th ACM Symposium on Principles and Practice of Parallel Programming, pp. 262\u2013277 (2022)","DOI":"10.1145\/3503221.3508444"},{"key":"476_CR3","doi-asserted-by":"crossref","unstructured":"Attiya, H., Ben-Baruch, O., Hendler, D.: Nesting-safe recoverable linearizability: modular constructions for non-volatile memory. In: Proc.\u00a0ACM Symposium on Principles of Distributed Computing, pp. 7\u201316 (2018)","DOI":"10.1145\/3212734.3212753"},{"key":"476_CR4","doi-asserted-by":"crossref","unstructured":"Beadle, H.A., Cai, W., Wen, H., Scott, M.L.: Nonblocking persistent software transactional memory. In: Proc.\u00a025th ACM Symposium on Principles and Practice of Parallel Programming, pp. 429\u2013430 (2020)","DOI":"10.1145\/3332466.3374506"},{"key":"476_CR5","doi-asserted-by":"crossref","unstructured":"Ben-David, N., Blelloch, G.E., Friedman, M., Wei, Y.: Delay-free concurrency on faulty persistent memory. In: Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures, pp. 253\u2013264 (2019)","DOI":"10.1145\/3323165.3323187"},{"key":"476_CR6","unstructured":"Berryhill, R., Golab, W.M., Tripunitara, M.: Robust shared objects for non-volatile main memory. In: Proc.\u00a019th International Conference on Principles of Distributed Systems, volume 46 of LIPIcs, pp. 20:1\u201320:17 (2015)"},{"issue":"10","key":"476_CR7","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1145\/2714064.2660224","volume":"49","author":"DR Chakrabarti","year":"2014","unstructured":"Chakrabarti, D.R., Boehm, H.-J., Bhandari, K.: Atlas: leveraging locks for non-volatile memory consistency. ACM SIGPLAN Notices 49(10), 433\u2013452 (2014)","journal-title":"ACM SIGPLAN Notices"},{"issue":"1","key":"476_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1145\/1961295.1950380","volume":"39","author":"J Coburn","year":"2011","unstructured":"Coburn, J., Caulfield, A.M., Akel, A., Grupp, L.M., Gupta, R.K., Jhala, R., Swanson, S.: NV-Heaps: making persistent objects fast and safe with next-generation, non-volatile memories. ACM SIGARCH Comput. Archit. News 39(1), 105\u2013118 (2011)","journal-title":"ACM SIGARCH Comput. Archit. News"},{"key":"476_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, N., Guerraoui, R., Zablotchi, I.: The inherent cost of remembering consistently. In: Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 259\u2013269 (2018)","DOI":"10.1145\/3210377.3210400"},{"key":"476_CR10","doi-asserted-by":"crossref","unstructured":"Correia, A., Felber, P., Ramalhete, P.: Romulus: efficient algorithms for persistent transactional memory. In: Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 271\u2013282 (2018)","DOI":"10.1145\/3210377.3210392"},{"key":"476_CR11","doi-asserted-by":"crossref","unstructured":"Correia, A, Felber, P., Ramalhete, P.: Persistent memory and the rise of universal constructions. In Proc. 15th European Conference on Computer Systems, pp. 5:1\u20135:15 (2020)","DOI":"10.1145\/3342195.3387515"},{"key":"476_CR12","doi-asserted-by":"crossref","unstructured":"Correia, A., Ramalhete, P., Felber, P.: A wait-free universal construction for large objects. In: Proc. 25th ACM Symposium on Principles and Practice of Parallel Programming, pp. 102\u2013116 (2020)","DOI":"10.1145\/3332466.3374523"},{"key":"476_CR13","doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fatourou, P., Fauconnier, H., Ruppert, E.: When is recoverable consensus harder than consensus? In: Proc.\u00a0ACM Symposium on Principles of Distributed Computing, pp. 198\u2013208 (2022)","DOI":"10.1145\/3519270.3538418"},{"issue":"3","key":"476_CR14","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s00224-013-9491-y","volume":"55","author":"P Fatourou","year":"2014","unstructured":"Fatourou, P., Kallimanis, N.D.: Highly-efficient wait-free synchronization. Theory Comput. Syst. 55(3), 475\u2013520 (2014)","journal-title":"Theory Comput. Syst."},{"key":"476_CR15","doi-asserted-by":"crossref","unstructured":"Fatourou, P., Kallimanis, N.D., Kosmas, E.: The performance power of software combining in persistence. In: Proc. 27th ACM Symposium on Principles and Practice of Parallel Programming, pp. 337\u2013352 (2022)","DOI":"10.1145\/3503221.3508426"},{"issue":"2\u20133","key":"476_CR16","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"F Fich","year":"2003","unstructured":"Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2\u20133), 121\u2013163 (2003)","journal-title":"Distrib. Comput."},{"issue":"2","key":"476_CR17","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"key":"476_CR18","doi-asserted-by":"crossref","unstructured":"Friedman, M., Ben-David, N., Wei, Y., Blelloch, G.E., Petrank, E.: NVTraverse: In NVRAM data structures, the destination is more important than the journey. In: Proc. 41st ACM Conference on Programming Language Design and Implementation, pp. 377\u2013392 (2020)","DOI":"10.1145\/3385412.3386031"},{"key":"476_CR19","doi-asserted-by":"crossref","unstructured":"Friedman, M., Petrank, E., Ramalhete, P.: Mirror: making lock-free data structures persistent. In: Proc. 42nd ACM Conference on Programming Language Design and Implementation, pp. 1218\u20131232 (2021)","DOI":"10.1145\/3453483.3454105"},{"key":"476_CR20","doi-asserted-by":"crossref","unstructured":"Golab, W.: The recoverable consensus hierarchy. In: Proc.\u00a032nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 281\u2013291 (2020). Extended version available from https:\/\/arxiv.org\/abs\/1804.10597","DOI":"10.1145\/3350755.3400212"},{"key":"476_CR21","doi-asserted-by":"crossref","unstructured":"Golab, W., Hendler, D.: Recoverable mutual exclusion under system-wide failures. In: Proc. ACM Symposium on Principles of Distributed Computing, pp. 17\u201326 (2018)","DOI":"10.1145\/3212734.3212755"},{"key":"476_CR22","doi-asserted-by":"crossref","unstructured":"Golab, W.M., Hendler, D.: Recoverable mutual exclusion in sub-logarithmic time. In: Proc. ACM Symposium on Principles of Distributed Computing, pp. 211\u2013220 (2017)","DOI":"10.1145\/3087801.3087819"},{"key":"476_CR23","doi-asserted-by":"crossref","unstructured":"Golab, W.M., Ramaraju, A.: Recoverable mutual exclusion. In: Proc. ACM Symposium on Principles of Distributed Computing, pp. 65\u201374 (2016)","DOI":"10.1145\/2933057.2933087"},{"key":"476_CR24","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Levy, R.R.: Robust emulations of shared memory in a crash-recovery model. In: Proc. 24th International Conference on Distributed Computing Systems, pp. 400\u2013407 (2004)","DOI":"10.1109\/ICDCS.2004.1281605"},{"issue":"1","key":"476_CR25","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. 13(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"476_CR26","doi-asserted-by":"crossref","unstructured":"Izraelevitz, J., Mendes, H., Scott, M.L.: Linearizability of persistent memory objects under a full-system-crash failure model. In: Proc. 30th International Symposium on Distributed Computing, volume 9888 of LNCS, pp. 313\u2013327 (2016)","DOI":"10.1007\/978-3-662-53426-7_23"},{"issue":"4","key":"476_CR27","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1145\/263867.263888","volume":"44","author":"P Jayanti","year":"1997","unstructured":"Jayanti, P.: Robust wait-free hierarchies. J. ACM 44(4), 592\u2013614 (1997)","journal-title":"J. ACM"},{"key":"476_CR28","unstructured":"K\u00f6nig, D.: \u00dcber eine Schlussweise aus dem Endlichen ins Unendliche. Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae: Sectio Scientiarum Mathematicarum, 3:121\u2013130 (1927). The required result also appears as Theorem 3 in chapter VI of K\u00f6nig\u2019s Theory of Finite and Infinite Graphs, Birkh\u00e4user, Boston (1990)"},{"key":"476_CR29","unstructured":"Li, N.: Detectable data structures for persistent memory. Master\u2019s thesis, University of Waterloo (2021). Available from https:\/\/uwspace.uwaterloo.ca\/handle\/10012\/16986"},{"issue":"3","key":"476_CR30","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."},{"key":"476_CR31","doi-asserted-by":"crossref","unstructured":"Neiger, G.: Failure detectors and the wait-free hierarchy. In: Proc. 14th ACM Symposium on Principles of Distributed Computing, pp. 100\u2013109 (1995)","DOI":"10.1145\/224964.224976"},{"key":"476_CR32","doi-asserted-by":"crossref","unstructured":"Ovens, S.: Determining recoverable consensus numbers. In: Proc. 43rd ACM Symposium on Principles of Distributed Computing, pp. 3\u201313 (2024)","DOI":"10.1145\/3662158.3662775"},{"key":"476_CR33","doi-asserted-by":"crossref","unstructured":"Ramalhete, P., Correia, A., Felber, P., Cohen, N.: OneFile: a wait-free persistent transactional memory. In: Proc. 49th IEEE\/IFIP International Conference on Dependable Systems and Networks, pp. 151\u2013163 (2019)","DOI":"10.1109\/DSN.2019.00028"},{"issue":"4","key":"476_CR34","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."},{"issue":"3","key":"476_CR35","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/1961296.1950379","volume":"46","author":"H Volos","year":"2011","unstructured":"Volos, H., Tack, A.J., Swift, M.M.: Mnemosyne: lightweight persistent memory. ACM SIGPLAN Notices 46(3), 91\u2013104 (2011)","journal-title":"ACM SIGPLAN Notices"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00476-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00476-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00476-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T10:50:06Z","timestamp":1747997406000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00476-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,7]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["476"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00476-w","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,2,7]]},"assertion":[{"value":"26 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2025","order":3,"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"}}]}}