{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:43Z","timestamp":1750220383137,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":18,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Science and Engineering Research Council of Canada","award":["RGPIN-2020-04178"],"award-info":[{"award-number":["RGPIN-2020-04178"]}]},{"name":"Ontario Graduate Scholarship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467906","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"497-507","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Reductions and Extension-Based Proofs"],"prefix":"10.1145","author":[{"given":"Kayman","family":"Brusse","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Faith","family":"Ellen","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316407"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405743"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_6"},{"key":"e_1_3_2_2_5_1","volume-title":"Proceedings of the 24'th International Conference on Principles of Distributed Systems (OPODIS). 18:1--18:16","author":"Attiya Hagit","year":"2020","unstructured":"Hagit Attiya , Armando Casta n eda, and Sergio Rajsbaum . 2020 . Locally Solvable Tasks and the Limitations of Valency Arguments . In Proceedings of the 24'th International Conference on Principles of Distributed Systems (OPODIS). 18:1--18:16 . https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2020.18 Hagit Attiya, Armando Casta n eda, and Sergio Rajsbaum. 2020. Locally Solvable Tasks and the Limitations of Valency Arguments. In Proceedings of the 24'th International Conference on Principles of Distributed Systems (OPODIS). 18:1--18:16. https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2020.18"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167119"},{"key":"e_1_3_2_2_7_1","volume-title":"Proceedings of the 12'th Annual ACM Symposium on Principles of Distributed Computing (PODC). 41--51","author":"Borowsky Elizabeth","year":"1993","unstructured":"Elizabeth Borowsky and Eli Gafni . 1993 b. Immediate Atomic Snapshots and Fast Renaming (Extended Abstract) . In Proceedings of the 12'th Annual ACM Symposium on Principles of Distributed Computing (PODC). 41--51 . https:\/\/doi.org\/10.1145\/164051.164056 Elizabeth Borowsky and Eli Gafni. 1993 b. Immediate Atomic Snapshots and Fast Renaming (Extended Abstract). In Proceedings of the 12'th Annual ACM Symposium on Principles of Distributed Computing (PODC). 41--51. https:\/\/doi.org\/10.1145\/164051.164056"},{"key":"e_1_3_2_2_8_1","volume-title":"Proceedings of the 16'th Annual ACM Symposium on Principles of Distributed Computing (PODC). 189--198","author":"Borowsky Elizabeth","year":"1997","unstructured":"Elizabeth Borowsky and Eli Gafni . 1997 . A Simple Algorithmically Reasoned Characterization of Wait-Free Computations . In Proceedings of the 16'th Annual ACM Symposium on Principles of Distributed Computing (PODC). 189--198 . https:\/\/doi.org\/10.1145\/259380.259439 Elizabeth Borowsky and Eli Gafni. 1997. A Simple Algorithmically Reasoned Characterization of Wait-Free Computations. In Proceedings of the 16'th Annual ACM Symposium on Principles of Distributed Computing (PODC). 189--198. https:\/\/doi.org\/10.1145\/259380.259439"},{"key":"e_1_3_2_2_9_1","first-page":"5","article-title":"New Combinatorial Topology Bounds for Renaming: the Lower Bound","volume":"22","author":"Sergio Rajsbaum Armando Casta","year":"2010","unstructured":"Armando Casta n eda and Sergio Rajsbaum . 2010 . New Combinatorial Topology Bounds for Renaming: the Lower Bound . Distributed Comput. , Vol. 22 , 5 -- 6 (2010), 287--301. https:\/\/doi.org\/10.1007\/s00446-010-0108-2 Armando Casta n eda and Sergio Rajsbaum. 2010. New Combinatorial Topology Bounds for Renaming: the Lower Bound. Distributed Comput., Vol. 22, 5--6 (2010), 287--301. https:\/\/doi.org\/10.1007\/s00446-010-0108-2","journal-title":"Distributed Comput."},{"key":"e_1_3_2_2_10_1","article-title":"Convergence and Covering on Graphs for Wait-free Robots","volume":"24","author":"Armando Casta","year":"2018","unstructured":"Armando Casta neda, Sergio Rajsbaum , and Matthieu Roy . 2018 . Convergence and Covering on Graphs for Wait-free Robots . J. Braz. Comput. Soc. , Vol. 24 , 1 (2018), 1:1--1:15. https:\/\/doi.org\/10.1186\/s13173-017-0065-8 Armando Casta neda, Sergio Rajsbaum, and Matthieu Roy. 2018. Convergence and Covering on Graphs for Wait-free Robots. J. Braz. Comput. Soc., Vol. 24, 1 (2018), 1:1--1:15. https:\/\/doi.org\/10.1186\/s13173-017-0065-8","journal-title":"J. Braz. Comput. Soc."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_2_2_12_1","volume-title":"Read-Write Reductions. In Proceedings of the 8'th International Conference on Distributed Computing and Networking (ICDCN). 349--354","author":"Gafni Eli","year":"2006","unstructured":"Eli Gafni . 2006 . Read-Write Reductions. In Proceedings of the 8'th International Conference on Distributed Computing and Networking (ICDCN). 349--354 . https:\/\/doi.org\/10.1007\/11947950_38 Eli Gafni. 2006. Read-Write Reductions. In Proceedings of the 8'th International Conference on Distributed Computing and Networking (ICDCN). 349--354. https:\/\/doi.org\/10.1007\/11947950_38"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.016"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_23"},{"key":"e_1_3_2_2_15_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"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397412"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307698"}],"event":{"name":"PODC '21: 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":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467906","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":18,"alternative-id":["10.1145\/3465084.3467906","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467906","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}