{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:55Z","timestamp":1750220335359,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":19,"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":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2020-04178"],"award-info":[{"award-number":["RGPIN-2020-04178"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538420","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"176-186","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Space Complexity of Consensus from Swap"],"prefix":"10.1145","author":[{"given":"Sean","family":"Ovens","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"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","volume-title":"Distributed Computing","volume":"6","author":"Anderson James H.","year":"1993","unstructured":"James H. Anderson . 1993 . Composite registers . Distributed Computing , Vol. 6 , 3 (01 Apr 1993), 141--154. https:\/\/doi.org\/10.1007\/BF02242703 10.1007\/BF02242703 James H. Anderson. 1993. Composite registers. Distributed Computing, Vol. 6, 3 (01 Apr 1993), 141--154. https:\/\/doi.org\/10.1007\/BF02242703"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90021-6"},{"key":"e_1_3_2_2_4_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 10.2200\/S00551ED1V01Y201311DCT012 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_5_1","volume-title":"TR2011--681","author":"Bowman Jack R.","year":"2011","unstructured":"Jack R. Bowman . 2011 . Obstruction-free Snapshot, Obstruction-free Consensus, and Fetch-and-add Modulo k . TR2011--681 (2011). Jack R. Bowman. 2011. Obstruction-free Snapshot, Obstruction-free Consensus, and Fetch-and-add Modulo k. TR2011--681 (2011)."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1065"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41848"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790192635"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314694"},{"key":"e_1_3_2_2_10_1","volume-title":"Distributed Computing","volume":"33","author":"Ellen Faith","year":"2020","unstructured":"Faith Ellen , Rati Gelashvili , Nir Shavit , and Leqi Zhu . 2020 . A complexity-based classification for multiprocessor synchronization . Distributed Computing , Vol. 33 , 2 (01 Apr 2020), 125--144. https:\/\/doi.org\/10.1007\/s00446-019-00361--3 10.1007\/s00446-019-00361--3 Faith Ellen, Rati Gelashvili, Nir Shavit, and Leqi Zhu. 2020. A complexity-based classification for multiprocessor synchronization. Distributed Computing, Vol. 33, 2 (01 Apr 2020), 125--144. https:\/\/doi.org\/10.1007\/s00446-019-00361--3"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212749"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290183"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"volume-title":"Distributed Computing","author":"Giakkoupis George","key":"e_1_3_2_2_14_1","unstructured":"George Giakkoupis , Maryam Helmi , Lisa Higham , and Philipp Woelfel . 2013. An mathcalO(sqrtn) Space Bound for Obstruction-Free Leader Election . In Distributed Computing . Springer Berlin Heidelberg , Berlin, Heidelberg , 46--60. George Giakkoupis, Maryam Helmi, Lisa Higham, and Philipp Woelfel. 2013. An mathcalO(sqrtn) Space Bound for Obstruction-Free Leader Election. In Distributed Computing. Springer Berlin Heidelberg, Berlin, Heidelberg, 46--60."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317299"},{"key":"e_1_3_2_2_17_1","volume-title":"Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing research","author":"Loui Michael C","year":"1987","unstructured":"Michael C Loui and Hosame H Abu-Amara . 1987. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing research , Vol. 4 , 163--183 ( 1987 ), 5--3. Michael C Loui and Hosame H Abu-Amara. 1987. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing research, Vol. 4, 163--183 (1987), 5--3."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467916"},{"key":"e_1_3_2_2_19_1","article-title":"A Tight Space Bound for Consensus","volume":"50","author":"Zhu Leqi","year":"2019","unstructured":"Leqi Zhu . 2019 . A Tight Space Bound for Consensus . SIAM J. Comput. , Vol. 50 , 3 (2019). https:\/\/doi.org\/10.1137\/16M1096785 A preliminary version appeared in STOC '16. 10.1137\/16M1096785 Leqi Zhu. 2019. A Tight Space Bound for Consensus. SIAM J. Comput., Vol. 50, 3 (2019). https:\/\/doi.org\/10.1137\/16M1096785 A preliminary version appeared in STOC '16.","journal-title":"SIAM J. Comput."}],"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.3538420","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538420","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.3538420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":19,"alternative-id":["10.1145\/3519270.3538420","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538420","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"}}]}}