{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:10:27Z","timestamp":1757617827904,"version":"3.44.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T00:00:00Z","timestamp":1744934400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T00:00:00Z","timestamp":1744934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007241","name":"Universit\u00e9 Paris-Saclay","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007241","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,9]]},"abstract":"Abstract<\/jats:title>\n We study two fundamental problems of distributed computing, consensus<\/jats:italic> and approximate agreement<\/jats:italic>, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem<\/jats:italic>. For a given n<\/jats:italic>-process task \n \n $$\\Pi $$<\/jats:tex-math>\n \n \u03a0<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and a given computational model M<\/jats:italic>, we define a new task, called the closure<\/jats:italic> of\u00a0\n \n $$\\Pi $$<\/jats:tex-math>\n \n \u03a0<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> with respect to\u00a0M<\/jats:italic>. The asynchronous speedup theorem states that if a task \n \n $$\\Pi $$<\/jats:tex-math>\n \n \u03a0<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is solvable in \n \n $$t\\ge 1$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> rounds in\u00a0M<\/jats:italic>, then its closure w.r.t.\u00a0M<\/jats:italic> is solvable in \n \n $$t-1$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> rounds in\u00a0M<\/jats:italic>. We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read\/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for \n \n $$n>2$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n ><\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster<\/jats:italic>. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read\/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.<\/jats:p>","DOI":"10.1007\/s00446-025-00480-0","type":"journal-article","created":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T15:45:21Z","timestamp":1744991121000},"page":"163-183","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A speedup theorem for asynchronous computation with applications to consensus and approximate agreement"],"prefix":"10.1007","volume":"38","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,18]]},"reference":[{"issue":"1","key":"480_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/16M1081439","volume":"48","author":"H Attiya","year":"2019","unstructured":"Attiya, H., Casta\u00f1eda, A., Herlihy, M., Paz, A.: Bounds on the step and namespace complexity of renaming. SIAM J. Comput. 48(1), 1\u201332 (2019)","journal-title":"SIAM J. Comput."},{"key":"480_CR2","doi-asserted-by":"crossref","unstructured":"Attiya, H., Ellen, F.: Impossibility Results for Distributed Computing. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2014)","DOI":"10.1007\/978-3-031-02010-0"},{"key":"480_CR3","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: 2nd ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 340\u2013349 (1990)","DOI":"10.1145\/97444.97701"},{"issue":"5","key":"480_CR4","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/3376902","volume":"63","author":"H Attiya","year":"2020","unstructured":"Attiya, H., Rajsbaum, S.: Indistinguishability. Commun. ACM 63(5), 90\u201399 (2020)","journal-title":"Commun. ACM"},{"key":"480_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.: Distributed Computing: Fundamentals. Simulations and Advanced Topics. John Wiley & Sons, Hoboken (2004)"},{"key":"480_CR6","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. In: 60th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 481\u2013497 (2019)","DOI":"10.1109\/FOCS.2019.00037"},{"key":"480_CR7","unstructured":"Bastide, P., Fraigniaud, P.: Brief annoucement: On extending Brandt\u2019s speedup theorem from LOCAL to round-based full-information models. In: 35th International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, pp. 47:1\u201347:4. Schloss Dagstuhl (2021)"},{"key":"480_CR8","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for $$t$$-resilient asynchronous computations. In: 25 ACM Symposium on Theory of Computing (STOC), pp. 91\u2013100 (1993)","DOI":"10.1145\/167088.167119"},{"key":"480_CR9","doi-asserted-by":"crossref","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)","DOI":"10.1145\/259380.259439"},{"key":"480_CR10","doi-asserted-by":"crossref","unstructured":"Bouzid, Z., Gafni, E., Kuznetsov, P.: Strong equivalence relations for iterated models. In: 18th International Conference on Principles of Distributed Systems (OPODIS), LNCS 8878, pp. 139\u2013154. Springer (2014)","DOI":"10.1007\/978-3-319-14472-6_10"},{"issue":"3\u20134","key":"480_CR11","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s41468-018-0011-7","volume":"1","author":"F Benavides","year":"2018","unstructured":"Benavides, F., Rajsbaum, S.: Collapsibility of read\/write models using discrete morse theory. J. Appl. Comput. Topol. 1(3\u20134), 365\u2013396 (2018)","journal-title":"J. Appl. Comput. Topol."},{"key":"480_CR12","doi-asserted-by":"crossref","unstructured":"Brandt, S.: An automatic speedup theorem for distributed problems. In: 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 379\u2013388 (2019)","DOI":"10.1145\/3293611.3331611"},{"key":"480_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.tcs.2020.10.012","volume":"849","author":"A Casta\u00f1eda","year":"2021","unstructured":"Casta\u00f1eda, A., Fraigniaud, P., Paz, A., Rajsbaum, S., Roy, M., Travers, C.: A topological perspective on distributed network algorithms. Theor. Comput. Sci. 849, 121\u2013137 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"480_CR14","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/S0097539798344367","volume":"34","author":"T Chandra","year":"2005","unstructured":"Chandra, T., Hadzilacos, V., Jayanti, P., Toueg, S.: Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus. SIAM J. Comput. 34(2), 333\u2013357 (2005)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"480_CR15","doi-asserted-by":"publisher","first-page":"45:1","DOI":"10.1145\/3266457","volume":"65","author":"A Casta\u00f1eda","year":"2018","unstructured":"Casta\u00f1eda, A., Rajsbaum, S., Raynal, M.: Unifying concurrent objects and distributed tasks: interval-linearizability. J. ACM 65(6), 45:1-45:42 (2018)","journal-title":"J. ACM"},{"issue":"3","key":"480_CR16","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)","journal-title":"J. ACM"},{"key":"480_CR17","doi-asserted-by":"crossref","unstructured":"Ellen, F., Gelashvili, R., Zhu, L.: Revisionist simulations: A new approach to proving space lower bounds. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC, pp. 61\u201370. ACM (2018)","DOI":"10.1145\/3212734.3212749"},{"issue":"2","key":"480_CR18","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)","journal-title":"J. ACM"},{"issue":"6","key":"480_CR19","doi-asserted-by":"publisher","first-page":"1","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), 1 (2021)","journal-title":"J. ACM"},{"key":"480_CR20","unstructured":"Fraigniaud, P., Paz, A.: The topology of local computing in networks. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP), vol.168 of LIPIcs, pp. 128:1\u2013128:18. Schloss Dagstuhl (2020)"},{"issue":"2\u20133","key":"480_CR21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"FE Fich","year":"2003","unstructured":"Fich, F.E., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2\u20133), 121\u2013163 (2003)","journal-title":"Distrib. Comput."},{"key":"480_CR22","doi-asserted-by":"crossref","unstructured":"Gafni, E., Guerraoui, R.: Generalized universality. In: Proceedings of the 22nd International Conference on Concurrency Theory, CONCUR\u201911, pp. 17\u201327. Springer-Verlag, Berlin, Heidelberg (2011)","DOI":"10.1007\/978-3-642-23217-6_2"},{"key":"480_CR23","doi-asserted-by":"crossref","unstructured":"Gafni, E., Rajsbaum, S.: Distributed programming with tasks. In: 14th International Conference on Principles of Distributed Systems (OPODIS), LNCS 6490, pp. 205\u2013218. Springer (2010)","DOI":"10.1007\/978-3-642-17653-1_17"},{"issue":"1","key":"480_CR24","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":"480_CR25","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":"480_CR26","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S.: Algebraic topology and distributed computing: a primer. In: Computer Science Today: Recent Trends and Developments, volume 1000 of LNCS, pp. 203\u2013217. Springer (1995)","DOI":"10.1007\/BFb0015245"},{"key":"480_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.04.007","volume":"683","author":"M Herlihy","year":"2017","unstructured":"Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: From wait-free to arbitrary concurrent solo executions in colorless distributed computing. Theor. Comput. Sci. 683, 1\u201321 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"480_CR28","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)","journal-title":"J. ACM"},{"key":"480_CR29","doi-asserted-by":"crossref","unstructured":"Hoest, G., Shavit, N.: Toward a topological characterization of asynchronous complexity. SIAM J. Comput. 36(2), 457\u2013497 (2006)","DOI":"10.1137\/S0097539701397412"},{"key":"480_CR30","doi-asserted-by":"crossref","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 9212, pp. 139\u2013155. Springer (2015)","DOI":"10.1007\/978-3-319-21741-3_10"},{"issue":"1","key":"480_CR31","doi-asserted-by":"publisher","first-page":"307","DOI":"10.4310\/HHA.2015.v17.n1.a15","volume":"17","author":"D Kozlov","year":"2015","unstructured":"Kozlov, D.: Topology of the view complex. Homol. Homotopy Appl. 17(1), 307\u2013319 (2015)","journal-title":"Homol. Homotopy Appl."},{"key":"480_CR32","doi-asserted-by":"crossref","unstructured":"Kuznetsov, P., Rieutord, T., He, Y.: An asynchronous computability theorem for fair adversaries. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC \u201918, pp. 387\u2013396, Association for Computing Machinery, New York, NY, USA (2018)","DOI":"10.1145\/3212734.3212765"},{"key":"480_CR33","doi-asserted-by":"crossref","unstructured":"Lynch, Nancy\u00a0A.: A hundred impossibility proofs for distributed computing. In: 8th ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201328 (1989)","DOI":"10.1145\/72981.72982"},{"issue":"4","key":"480_CR34","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/S0097539799364006","volume":"31","author":"Y Moses","year":"2002","unstructured":"Moses, Y., Rajsbaum, S.: A layered analysis of consensus. SIAM J. Comput. 31(4), 989\u20131021 (2002)","journal-title":"SIAM J. Comput."},{"issue":"5\u20136","key":"480_CR35","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/S0020-0190(00)00027-2","volume":"73","author":"A Mostefaoui","year":"2000","unstructured":"Mostefaoui, A., Raynal, M., Tronel, F.: From binary consensus to multivalued consensus in asynchronous message-passing systems. Inf. Process. Lett. 73(5\u20136), 207\u2013212 (2000)","journal-title":"Inf. Process. Lett."},{"key":"480_CR36","doi-asserted-by":"crossref","unstructured":"Rajsbaum, S.: Iterated shared memory models. In: L\u00f3pez-Ortiz, Alejandro (ed), LATIN 2010: Theoretical Informatics, pp. 407\u2013416. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)","DOI":"10.1007\/978-3-642-12200-2_36"},{"key":"480_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94141-7","volume-title":"Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach","author":"M Raynal","year":"2018","unstructured":"Raynal, M.: Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer, Cham (2018)"},{"key":"480_CR38","unstructured":"Rieutord, T.: Combinatorial characterization of asynchronous distributed computability. (Caract\u00e9risation combinatoire de la calculabilit\u00e9 distribu\u00e9e asynchrone). PhD thesis, University of Paris-Saclay, France (2018)"},{"key":"480_CR39","doi-asserted-by":"crossref","unstructured":"Saks, M.E., Zaharoglou, F.: Wait-free $$k$$-set agreement is impossible: the topology of public knowledge. In: 25th ACM Symposium on Theory of Computing (STOC), pp. 101\u2013110 (1993)","DOI":"10.1145\/167088.167122"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00480-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00480-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00480-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T11:42:14Z","timestamp":1757158934000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00480-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,18]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["480"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00480-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,4,18]]},"assertion":[{"value":"18 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 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 have no Conflict of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}