{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:54Z","timestamp":1750220334966,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["DUCAT"],"award-info":[{"award-number":["DUCAT"]}]},{"name":"UNAM-PAPIIT","award":["IN106520"],"award-info":[{"award-number":["IN106520"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538422","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"460-470","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement"],"prefix":"10.1145","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"IRIF, CNRS & Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[{"name":"LISN, CNRS & Universit\u00e9 Paris Saclay, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[{"name":"UNAM, Mexico city, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"volume-title":"Wait-Free Data Structures in the Asynchronous PRAM Model. In 2nd ACM Symposium on Parallel Algorithms and Architectures (SPAA) (Island of Crete, Greece). 340--349","author":"Aspnes J.","key":"e_1_3_2_2_1_1","unstructured":"J. Aspnes and M. Herlihy . 1990 . Wait-Free Data Structures in the Asynchronous PRAM Model. In 2nd ACM Symposium on Parallel Algorithms and Architectures (SPAA) (Island of Crete, Greece). 340--349 . https:\/\/doi.org\/10.1145\/97444.97701 10.1145\/97444.97701 J. Aspnes and M. Herlihy. 1990. Wait-Free Data Structures in the Asynchronous PRAM Model. In 2nd ACM Symposium on Parallel Algorithms and Architectures (SPAA) (Island of Crete, Greece). 340--349. https:\/\/doi.org\/10.1145\/97444.97701"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1081439"},{"key":"e_1_3_2_2_3_1","volume-title":"Impossibility Results for Distributed Computing","author":"Attiya Hagit","year":"2013","unstructured":"Hagit Attiya and Faith Ellen . 2014. Impossibility Results for Distributed Computing . Morgan & Claypool Publishers . https:\/\/doi.org\/10.2200\/ S00551ED1V01Y 2013 11DCT012 Hagit Attiya and Faith Ellen. 2014. Impossibility Results for Distributed Computing. Morgan & Claypool Publishers. https:\/\/doi.org\/10.2200\/ S00551ED1V01Y201311DCT012"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376902"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_3_2_2_6_1","volume-title":"Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Symposium on Foundations of Computer Science (FOCS). 481--497","author":"Balliu Alkida","year":"2019","unstructured":"Alkida Balliu , Sebastian Brandt , Juho Hirvonen , Dennis Olivetti , Mika\u00ebl Rabie , and Jukka Suomela . 2019 . Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Symposium on Foundations of Computer Science (FOCS). 481--497 . https:\/\/doi.org\/10.1109\/FOCS.2019.00037 10.1109\/FOCS.2019.00037 Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2019. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Symposium on Foundations of Computer Science (FOCS). 481--497. https:\/\/doi.org\/10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_2_7_1","volume-title":"35th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"4","author":"Bastide Paul","year":"2021","unstructured":"Paul Bastide and Pierre Fraigniaud . 2021 . Brief Annoucement: On Extending Brandt's Speedup Theorem from LOCAL to Round-Based Full-Information Models . In 35th International Symposium on Distributed Computing (DISC) (LIPIcs , Vol. 209). Schloss Dagstuhl, 47:1--47: 4 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.47 10.4230\/LIPIcs.DISC.2021.47 Paul Bastide and Pierre Fraigniaud. 2021. Brief Annoucement: On Extending Brandt's Speedup Theorem from LOCAL to Round-Based Full-Information Models. In 35th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 209). Schloss Dagstuhl, 47:1--47:4. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.47"},{"key":"e_1_3_2_2_8_1","first-page":"3","article-title":"Collapsibility of read\/write models using discrete morse theory","volume":"1","author":"Benavides Fernando","year":"2018","unstructured":"Fernando Benavides and Sergio Rajsbaum . 2018 . Collapsibility of read\/write models using discrete morse theory . J. Appl. Comput. Topol. 1 , 3 -- 4 (2018), 365--396. https:\/\/doi.org\/10.1007\/s41468-018-0011--7 10.1007\/s41468-018-0011--7 Fernando Benavides and Sergio Rajsbaum. 2018. Collapsibility of read\/write models using discrete morse theory. J. Appl. Comput. Topol. 1, 3--4 (2018), 365--396. https:\/\/doi.org\/10.1007\/s41468-018-0011--7","journal-title":"J. Appl. Comput. Topol."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167119"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259439"},{"key":"e_1_3_2_2_11_1","volume-title":"Strong Equivalence Relations for Iterated Models. In 18th International Conference on Principles of Distributed Systems (OPODIS) (LNCS 8878)","author":"Bouzid Zohir","year":"2014","unstructured":"Zohir Bouzid , Eli Gafni , and Petr Kuznetsov . 2014 . Strong Equivalence Relations for Iterated Models. In 18th International Conference on Principles of Distributed Systems (OPODIS) (LNCS 8878) . Springer, 139--154. https:\/\/doi.org\/10.1007\/978- 3--319--14472--6_10 10.1007\/978- Zohir Bouzid, Eli Gafni, and Petr Kuznetsov. 2014. Strong Equivalence Relations for Iterated Models. In 18th International Conference on Principles of Distributed Systems (OPODIS) (LNCS 8878). Springer, 139--154. https:\/\/doi.org\/10.1007\/978- 3--319--14472--6_10"},{"key":"e_1_3_2_2_12_1","volume-title":"An Automatic Speedup Theorem for Distributed Problems. In 38th ACM Symposium on Principles of Distributed Computing (PODC). 379--388","author":"Brandt Sebastian","year":"2019","unstructured":"Sebastian Brandt . 2019 . An Automatic Speedup Theorem for Distributed Problems. In 38th ACM Symposium on Principles of Distributed Computing (PODC). 379--388 . https:\/\/doi.org\/10.1145\/3293611.3331611 10.1145\/3293611.3331611 Sebastian Brandt. 2019. An Automatic Speedup Theorem for Distributed Problems. In 38th ACM Symposium on Principles of Distributed Computing (PODC). 379--388. https:\/\/doi.org\/10.1145\/3293611.3331611"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.10.012"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798344367"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5931"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212749"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-003-0091-y"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_2_2_19_1","first-page":"1","article-title":"The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 168)","volume":"128","author":"Fraigniaud Pierre","year":"2020","unstructured":"Pierre Fraigniaud and Ami Paz . 2020 . The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 168) . Schloss Dagstuhl , 128 : 1 -- 128 :18. https: \/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.128 10.4230\/LIPIcs.ICALP.2020.128 Pierre Fraigniaud and Ami Paz. 2020. The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 168). Schloss Dagstuhl, 128:1--128:18. https: \/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.128","journal-title":"Schloss Dagstuhl"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485242"},{"key":"e_1_3_2_2_21_1","volume-title":"Generalized Universality. In Proceedings of the 22nd International Conference on Concurrency Theory","author":"Gafni Eli","year":"2011","unstructured":"Eli Gafni and Rachid Guerraoui . 2011 . Generalized Universality. In Proceedings of the 22nd International Conference on Concurrency Theory ( Aachen, Germany) (CONCUR'11). Springer-Verlag, Berlin, Heidelberg, 17--27. Eli Gafni and Rachid Guerraoui. 2011. Generalized Universality. In Proceedings of the 22nd International Conference on Concurrency Theory (Aachen, Germany) (CONCUR'11). Springer-Verlag, Berlin, Heidelberg, 17--27."},{"key":"e_1_3_2_2_22_1","volume-title":"Distributed Programming with Tasks. In 14th International Conference on Principles of Distributed Systems (OPODIS) (LNCS 6490)","author":"Gafni Eli","year":"2010","unstructured":"Eli Gafni and Sergio Rajsbaum . 2010 . Distributed Programming with Tasks. In 14th International Conference on Principles of Distributed Systems (OPODIS) (LNCS 6490) . Springer, 205--218. https:\/\/doi.org\/10.1007\/978--3--642--17653--1_17 10.1007\/978--3--642--17653--1_17 Eli Gafni and Sergio Rajsbaum. 2010. Distributed Programming with Tasks. In 14th International Conference on Principles of Distributed Systems (OPODIS) (LNCS 6490). Springer, 205--218. https:\/\/doi.org\/10.1007\/978--3--642--17653--1_17"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Maurice Herlihy Dmitry N. Kozlov and Sergio Rajsbaum. 2013. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann.  Maurice Herlihy Dmitry N. Kozlov and Sergio Rajsbaum. 2013. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann.","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"volume-title":"Computer Science Today: Recent Trends and Developments. LNCS","author":"Herlihy Maurice","key":"e_1_3_2_2_25_1","unstructured":"Maurice Herlihy and Sergio Rajsbaum . 1995. Algebraic Topology and Distributed Computing: A Primer . In Computer Science Today: Recent Trends and Developments. LNCS , Vol. 1000 . Springer , 203--217. https:\/\/doi.org\/10.1007\/BFb0015245 10.1007\/BFb0015245 Maurice Herlihy and Sergio Rajsbaum. 1995. Algebraic Topology and Distributed Computing: A Primer. In Computer Science Today: Recent Trends and Developments. LNCS, Vol. 1000. Springer, 203--217. https:\/\/doi.org\/10.1007\/BFb0015245"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.04.007"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397412"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21741-3_10"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.4310\/HHA.2015.v17.n1.a15"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212765"},{"key":"e_1_3_2_2_32_1","volume-title":"AHundred Impossibility Proofs for Distributed Computing. In 8th ACM Symposium on Principles of Distributed Computing (PODC). 1--28","author":"Lynch Nancy A.","year":"1989","unstructured":"Nancy A. Lynch . 1989 . AHundred Impossibility Proofs for Distributed Computing. In 8th ACM Symposium on Principles of Distributed Computing (PODC). 1--28 . https:\/\/doi.org\/10.1145\/72981.72982 10.1145\/72981.72982 Nancy A. Lynch. 1989. AHundred Impossibility Proofs for Distributed Computing. In 8th ACM Symposium on Principles of Distributed Computing (PODC). 1--28. https:\/\/doi.org\/10.1145\/72981.72982"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364006"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00027-2"},{"volume-title":"LATIN 2010: Theoretical Informatics, Alejandro L\u00f3pez-Ortiz (Ed.)","author":"Rajsbaum Sergio","key":"e_1_3_2_2_35_1","unstructured":"Sergio Rajsbaum . 2010. Iterated Shared Memory Models . In LATIN 2010: Theoretical Informatics, Alejandro L\u00f3pez-Ortiz (Ed.) . Springer Berlin Heidelberg, Berlin , Heidelberg , 407--416. Sergio Rajsbaum. 2010. Iterated Shared Memory Models. In LATIN 2010: Theoretical Informatics, Alejandro L\u00f3pez-Ortiz (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 407--416."},{"volume-title":"Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach","author":"Raynal Michel","key":"e_1_3_2_2_36_1","unstructured":"Michel Raynal . 2018. Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach . Springer . https:\/\/doi.org\/10.1007\/978--3--319--94141--7 10.1007\/978--3--319--94141--7 Michel Raynal. 2018. Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer. https:\/\/doi.org\/10.1007\/978--3--319--94141--7"},{"volume-title":"25th ACM Symposium on Theory of Computing (STOC). 101--110","author":"Michael","key":"e_1_3_2_2_37_1","unstructured":"Michael E. Saks and Fotios Zaharoglou. 1993. Wait-free -set agreement is impossible: the topology of public knowledge . In 25th ACM Symposium on Theory of Computing (STOC). 101--110 . https:\/\/doi.org\/10.1145\/167088.167122 10.1145\/167088.167122 Michael E. Saks and Fotios Zaharoglou. 1993. Wait-free -set agreement is impossible: the topology of public knowledge. In 25th ACM Symposium on Theory of Computing (STOC). 101--110. https:\/\/doi.org\/10.1145\/167088.167122"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538422","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538422","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":37,"alternative-id":["10.1145\/3519270.3538422","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538422","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}