{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T02:18:25Z","timestamp":1774059505535,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T00:00:00Z","timestamp":1768780800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T00:00:00Z","timestamp":1768780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE48-0006"],"award-info":[{"award-number":["ANR-20-CE48-0006"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE48-0006"],"award-info":[{"award-number":["ANR-20-CE48-0006"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE48-0006"],"award-info":[{"award-number":["ANR-20-CE48-0006"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE48-0006"],"award-info":[{"award-number":["ANR-20-CE48-0006"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE48-0006"],"award-info":[{"award-number":["ANR-20-CE48-0006"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s00446-025-00492-w","type":"journal-article","created":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T06:37:27Z","timestamp":1768804647000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The computational power of distributed shared-memory models with bounded-size registers"],"prefix":"10.1007","volume":"39","author":[{"given":"Carole","family":"Delporte-Gallet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugues","family":"Fauconnier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Corentin","family":"Travers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,19]]},"reference":[{"key":"492_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Amit, Y., Dolev, D.: Optimal resilience asynchronous approximate agreement. In: 8th International Conference on Principles of Distributed Systems (OPODIS). LNCS, vol. 3544, pp. 229\u2013239. Springer (2004), https:\/\/doi.org\/10.1007\/11516798_17","DOI":"10.1007\/11516798_17"},{"issue":"4","key":"492_CR2","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). https:\/\/doi.org\/10.1145\/153724.153741","journal-title":"J. ACM"},{"key":"492_CR3","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.tcs.2014.07.022","volume":"561","author":"Y Afek","year":"2015","unstructured":"Afek, Y., Gafni, E.: A simple characterization of asynchronous computations. Theoretical Computer Science 561, 88\u201395 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.07.022","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"492_CR4","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/200836.200869","volume":"42","author":"H Attiya","year":"1995","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM 42(1), 124\u2013142 (1995). https:\/\/doi.org\/10.1145\/200836.200869","journal-title":"J. ACM"},{"key":"492_CR5","doi-asserted-by":"publisher","unstructured":"Attiya, H., Ellen, F.: The step complexity of multidimensional approximate agreement. In: 26th International Conference on Principles of Distributed Systems (OPODIS). LIPIcs, vol. 253, pp. 6:1\u20136:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022), https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2022.6","DOI":"10.4230\/LIPIcs.OPODIS.2022.6"},{"issue":"4","key":"492_CR6","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1137\/S0097539797330689","volume":"31","author":"H Attiya","year":"2002","unstructured":"Attiya, H., Rajsbaum, S.: The combinatorial structure of wait-free solvable tasks. SIAM J. Comput. 31(4), 1286\u20131313 (2002). https:\/\/doi.org\/10.1137\/S0097539797330689","journal-title":"SIAM J. Comput."},{"key":"492_CR7","doi-asserted-by":"crossref","unstructured":"Attiya, H., Welch, J.: Distributed computing: fundamentals, simulations, and advanced topics. Presented at the (2004)","DOI":"10.1002\/0471478210"},{"issue":"5","key":"492_CR8","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1145\/362946.362970","volume":"12","author":"KA Bartlett","year":"1969","unstructured":"Bartlett, K.A., Scantlebury, R.A., Wilkinson, P.T.: A note on reliable full-duplex transmission over half-duplex links. Commun. ACM 12(5), 260\u2013261 (1969)","journal-title":"Commun. ACM"},{"issue":"3","key":"492_CR9","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/0196-6774(90)90020-F","volume":"11","author":"O Biran","year":"1990","unstructured":"Biran, O., Moran, S., Zaks, S.: A combinatorial characterization of the distributed 1-solvable tasks. Journal of Algorithms 11(3), 420\u2013440 (1990). https:\/\/doi.org\/10.1016\/0196-6774(90)90020-F","journal-title":"Journal of Algorithms"},{"key":"492_CR10","doi-asserted-by":"publisher","unstructured":"Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming (extended abstract). In: 12th ACM Symposium on Principles of Distributed Computing (PODC). pp. 41\u201351 (1993), https:\/\/doi.org\/10.1145\/164051.164056","DOI":"10.1145\/164051.164056"},{"key":"492_CR11","doi-asserted-by":"publisher","unstructured":"Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computations (extended abstract). In: 16th ACM Symposium on Principles of Distributed Computing (PODC). pp. 189\u2013198 (1997), https:\/\/doi.org\/10.1145\/259380.259439","DOI":"10.1145\/259380.259439"},{"issue":"3","key":"492_CR12","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.cosrev.2011.04.001","volume":"5","author":"A Casta\u00f1eda","year":"2011","unstructured":"Casta\u00f1eda, A., Rajsbaum, S., Raynal, M.: The renaming problem in shared memory systems: An introduction. Comput. Sci. Rev. 5(3), 229\u2013251 (2011). https:\/\/doi.org\/10.1016\/j.cosrev.2011.04.001","journal-title":"Comput. Sci. Rev."},{"key":"492_CR13","doi-asserted-by":"publisher","unstructured":"Delporte-Gallet, C., Fauconnier, H., Rajsbaum, S.: Communication complexity of wait-free computability in dynamic networks. In: 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 12156, pp. 291\u2013309. Springer (2020), https:\/\/doi.org\/10.1007\/978-3-030-54921-3_17","DOI":"10.1007\/978-3-030-54921-3_17"},{"key":"492_CR14","unstructured":"Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. In: 3rd IEEE Symp. on Reliability in Distributed Software and Database Systems (SRDS). pp. 145\u2013154 (1983)"},{"issue":"3","key":"492_CR15","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/5925.5931","volume":"33","author":"D Dolev","year":"1986","unstructured":"Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499\u2013516 (1986). https:\/\/doi.org\/10.1145\/5925.5931","journal-title":"J. ACM"},{"issue":"2","key":"492_CR16","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.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985). https:\/\/doi.org\/10.1145\/3149.214121","journal-title":"J. ACM"},{"issue":"6","key":"492_CR17","doi-asserted-by":"publisher","first-page":"4:61","DOI":"10.1145\/3485242","volume":"68","author":"M F\u00fcgger","year":"2021","unstructured":"F\u00fcgger, M., Nowak, T., Schwarz, M.: Tight bounds for asymptotic and approximate consensus. J. ACM 68(6), 4:61-4:635 (2021)","journal-title":"J. ACM"},{"issue":"3","key":"492_CR18","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1137\/S0097539796305766","volume":"28","author":"E Gafni","year":"1999","unstructured":"Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Comput. 28(3), 970\u2013983 (1999)","journal-title":"SIAM J. Comput."},{"key":"492_CR19","doi-asserted-by":"publisher","unstructured":"Gafni, E., Rajsbaum, S.: Distributed programming with tasks. In: 14th International Conference on Principles of Distributed Systems (OPODIS). LNCS, vol. 6490, pp. 205\u2013218. Springer (2010), https:\/\/doi.org\/10.1007\/978-3-642-17653-1_17","DOI":"10.1007\/978-3-642-17653-1_17"},{"issue":"10","key":"492_CR20","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1017\/S0960129521000037","volume":"30","author":"E Godard","year":"2020","unstructured":"Godard, E., Perdereau, E.: Back to the coordinated attack problem. Mathematical Structures in Computer Science 30(10), 1089\u20131113 (2020). https:\/\/doi.org\/10.1017\/S0960129521000037","journal-title":"Mathematical Structures in Computer Science"},{"issue":"1","key":"492_CR21","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). https:\/\/doi.org\/10.1145\/114005.102808","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"492_CR22","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Kozlov, D.N., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann (2013)","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"492_CR23","doi-asserted-by":"publisher","unstructured":"Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks. In: 29th ACM Symposium on the Theory of Computing (STOC). pp. 589\u2013598 (1997), https:\/\/doi.org\/10.1145\/258533.258652","DOI":"10.1145\/258533.258652"},{"issue":"6","key":"492_CR24","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1145\/331524.331529","volume":"46","author":"M Herlihy","year":"1999","unstructured":"Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858\u2013923 (1999). https:\/\/doi.org\/10.1145\/331524.331529","journal-title":"J. ACM"},{"issue":"2","key":"492_CR25","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/S0097539701397412","volume":"36","author":"G Hoest","year":"2006","unstructured":"Hoest, G., Shavit, N.: Toward a topological characterization of asynchronous complexity. SIAM J. Comput. 36(2), 457\u2013497 (2006). https:\/\/doi.org\/10.1137\/S0097539701397412","journal-title":"SIAM J. Comput."},{"key":"492_CR26","doi-asserted-by":"publisher","unstructured":"Imbs, D., Rajsbaum, S., Valle, A.: Untangling partial agreement: Iterated x-consensus simulations. In: 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). LNCS, vol. 9212, pp. 139\u2013155. Springer (2015), https:\/\/doi.org\/10.1007\/978-3-319-21741-3_10","DOI":"10.1007\/978-3-319-21741-3_10"},{"key":"492_CR27","doi-asserted-by":"publisher","unstructured":"Kuznetsov, P., Rieutord, T.: Affine tasks for k-test-and-set. In: 22nd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). LNCS, vol. 12514, pp. 151\u2013166. Springer (2020), https:\/\/doi.org\/10.1007\/978-3-030-64348-5_12","DOI":"10.1007\/978-3-030-64348-5_12"},{"key":"492_CR28","doi-asserted-by":"crossref","unstructured":"Kuznetsov, P., Rieutord, T., He, Y.: An asynchronous computability theorem for fair adversaries. In: 37th ACM Symposium on Principles of Distributed Computing (PODC). pp. 387\u2013396 (2018), https:\/\/dl.acm.org\/citation.cfm?id=3212765","DOI":"10.1145\/3212734.3212765"},{"issue":"6","key":"492_CR29","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/363347.363366","volume":"11","author":"WC Lynch","year":"1968","unstructured":"Lynch, W.C.: Computer systems: Reliable full-duplex file transmission over half-duplex telephone line. Commun. ACM 11(6), 407\u2013410 (1968)","journal-title":"Commun. ACM"},{"key":"492_CR30","doi-asserted-by":"publisher","unstructured":"Moran, S.: Using approximate agreement to obtain complete disagreement: The output structure of input-free asynchronous computations. In: 3rd Israel Symposium on Theory of Computing and Systems (ISTCS). pp. 251\u2013257. IEEE (1995), https:\/\/doi.org\/10.1109\/ISTCS.1995.377025","DOI":"10.1109\/ISTCS.1995.377025"},{"issue":"7","key":"492_CR31","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/TIT.2003.813496","volume":"49","author":"A Orlitsky","year":"2003","unstructured":"Orlitsky, A., Viswanathan, K.: One-way communication and error-correcting codes. IEEE Transactions on Information Theory 49(7), 1781\u20131788 (2003). https:\/\/doi.org\/10.1109\/TIT.2003.813496","journal-title":"IEEE Transactions on Information Theory"},{"key":"492_CR32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113761","volume":"952","author":"S Rajsbaum","year":"2023","unstructured":"Rajsbaum, S.: A distributed computing perspective of unconditionally secure information transmission in russian cards problems. Theoretical Computer Science 952, 113761 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2023.113761","journal-title":"Theoretical Computer Science"},{"key":"492_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32027-9","volume-title":"Concurrent Programming - Algorithms, Principles, and Foundations","author":"M Raynal","year":"2013","unstructured":"Raynal, M.: Concurrent Programming - Algorithms, Principles, and Foundations. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-32027-9"},{"key":"492_CR34","doi-asserted-by":"publisher","unstructured":"Raynal, M.: Set agreement. In: Encyclopedia of Algorithms, pp. 1956\u20131959. Springer (2016), https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_367","DOI":"10.1007\/978-1-4939-2864-4_367"},{"key":"492_CR35","doi-asserted-by":"publisher","unstructured":"Saraph, V., Herlihy, M., Gafni, E.: Asynchronous computability theorems for $$t$$-resilient systems. In: 30th International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol.\u00a09888, pp. 428\u2013441. Springer (2016), https:\/\/doi.org\/10.1007\/978-3-662-53426-7_31","DOI":"10.1007\/978-3-662-53426-7_31"},{"key":"492_CR36","doi-asserted-by":"publisher","unstructured":"Schenk, E.: Faster approximate agreement with multi-writer registers. In: 36th IEEE Symposium on Foundations of Computer Science (FOCS). pp. 714\u2013723 (1995), https:\/\/doi.org\/10.1109\/SFCS.1995.492673","DOI":"10.1109\/SFCS.1995.492673"},{"key":"492_CR37","unstructured":"Schenk, E.: Computability and complexity results for agreement problems in shared memory distributed systems. Ph.D. thesis, University of Toronto, Canada (1996), https:\/\/librarysearch.library.utoronto.ca\/permalink\/01UTORONTO_INST\/14bjeso\/alma991106419166406196"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00492-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00492-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00492-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T01:45:44Z","timestamp":1774057544000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00492-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,19]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["492"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00492-w","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,19]]},"assertion":[{"value":"5 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2026","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"}}],"article-number":"4"}}