{"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":1750220383018,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":35,"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":"Ontario Graduate Scholarship (OGS) Program"},{"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":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467916","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"509-519","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Space Complexity of Scannable Binary Objects"],"prefix":"10.1145","author":[{"given":"Sean","family":"Ovens","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]}],"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","volume-title":"Composite Registers. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing (Quebec City","author":"Anderson James","year":"1990","unstructured":"James Anderson . 1990 . Composite Registers. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing (Quebec City , Quebec, Canada) (PODC '90). Association for Computing Machinery, New York, NY, USA, 15--29. https:\/\/doi.org\/10.1145\/93385.93396 James Anderson. 1990. Composite Registers. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing (Quebec City, Quebec, Canada) (PODC '90). Association for Computing Machinery, New York, NY, USA, 15--29. https:\/\/doi.org\/10.1145\/93385.93396"},{"key":"e_1_3_2_2_3_1","volume-title":"Multi-writer composite registers. Distributed Computing 7, 4 (01","author":"Anderson James H.","year":"1994","unstructured":"James H. Anderson . 1994. Multi-writer composite registers. Distributed Computing 7, 4 (01 May 1994 ), 175--195. https:\/\/doi.org\/10.1007\/BF02280833 James H. Anderson. 1994. Multi-writer composite registers. Distributed Computing 7, 4 (01 May 1994), 175--195. https:\/\/doi.org\/10.1007\/BF02280833"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582728"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2732263"},{"volume-title":"Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures (Island of Crete, Greece) (SPAA '90)","author":"Aspnes J.","key":"e_1_3_2_2_6_1","unstructured":"J. Aspnes and M. Herlihy . 1990. Wait-Free Data Structures in the Asynchronous PRAM Model . In Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures (Island of Crete, Greece) (SPAA '90) . Association for Computing Machinery, New York, NY, USA, 340--349. https:\/\/doi.org\/10.1145\/ 97444.97701 J. Aspnes and M. Herlihy. 1990. Wait-Free Data Structures in the Asynchronous PRAM Model. In Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures (Island of Crete, Greece) (SPAA '90). Association for Computing Machinery, New York, NY, USA, 340--349. https:\/\/doi.org\/10.1145\/ 97444.97701"},{"key":"e_1_3_2_2_7_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_8_1","volume-title":"Atomic snapshots using lattice agreement. Distributed Computing 8, 3 (01","author":"Attiya Hagit","year":"1995","unstructured":"Hagit Attiya , Maurice Herlihy , and Ophir Rachman . 1995. Atomic snapshots using lattice agreement. Distributed Computing 8, 3 (01 Mar 1995 ), 121--132. https:\/\/doi.org\/10.1007\/BF02242714 Hagit Attiya, Maurice Herlihy, and Ophir Rachman. 1995. Atomic snapshots using lattice agreement. Distributed Computing 8, 3 (01 Mar 1995), 121--132. https:\/\/doi.org\/10.1007\/BF02242714"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795279463"},{"key":"e_1_3_2_2_10_1","volume-title":"Welch","author":"Attiya Hagit","year":"2004","unstructured":"Hagit Attiya and Jennifer L . Welch . 2004 . Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley . Hagit Attiya and Jennifer L. Welch. 2004. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0301-7"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1065"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314694"},{"key":"e_1_3_2_2_14_1","volume-title":"The space complexity of unbounded timestamps. Distributed Computing 21, 2 (01","author":"Ellen Faith","year":"2008","unstructured":"Faith Ellen , Panagiota Fatourou , and Eric Ruppert . 2008. The space complexity of unbounded timestamps. Distributed Computing 21, 2 (01 Jul 2008 ), 103--115. https:\/\/doi.org\/10.1007\/s00446-008-0060--6 Faith Ellen, Panagiota Fatourou, and Eric Ruppert. 2008. The space complexity of unbounded timestamps. Distributed Computing 21, 2 (01 Jul 2008), 103--115. https:\/\/doi.org\/10.1007\/s00446-008-0060--6"},{"key":"e_1_3_2_2_15_1","volume-title":"A complexity-based classification for multiprocessor synchronization. Distributed Computing 33, 2 (01","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 33, 2 (01 Apr 2020 ), 125--144. https:\/\/doi.org\/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 33, 2 (01 Apr 2020), 125--144. https:\/\/doi.org\/10.1007\/s00446-019-00361--3"},{"key":"e_1_3_2_2_16_1","volume-title":"Kallimanis","author":"Fatourou Panagiota","year":"2017","unstructured":"Panagiota Fatourou and Nikolaos D . Kallimanis . 2017 . Lower and upper bounds for single-scanner snapshot implementations. Distributed Computing 30, 4 (01 Aug 2017), 231--260. https:\/\/doi.org\/10.1007\/s00446-016-0286--7 Panagiota Fatourou and Nikolaos D. Kallimanis. 2017. Lower and upper bounds for single-scanner snapshot implementations. Distributed Computing 30, 4 (01 Aug 2017), 231--260. https:\/\/doi.org\/10.1007\/s00446-016-0286--7"},{"key":"e_1_3_2_2_17_1","volume-title":"Hundreds of impossibility results for distributed computing. Distributed Computing 16, 2 (01","author":"Fich Faith","year":"2003","unstructured":"Faith Fich and Eric Ruppert . 2003. Hundreds of impossibility results for distributed computing. Distributed Computing 16, 2 (01 Sep 2003 ), 121--163. https:\/\/doi.org\/ 10.1007\/s00446-003-0091-y Faith Fich and Eric Ruppert. 2003. Hundreds of impossibility results for distributed computing. Distributed Computing 16, 2 (01 Sep 2003), 121--163. https:\/\/doi.org\/ 10.1007\/s00446-003-0091-y"},{"key":"e_1_3_2_2_18_1","volume-title":"ISTCS'92","volume":"183","author":"Gawlick Rainer","year":"1992","unstructured":"Rainer Gawlick , Nancy A. Lynch , and Nir Shavit . 1992 . Concurrent Timestamping Made Simple. In Theory of Computing and Systems , ISTCS'92 , Israel Symposium, Haifa, Israel , May 1992 (Lecture Notes in Computer Science, Vol. 601), Danny Dolev, Zvi Galil, and Michael Rodeh (Eds.). Springer, 171-- 183 . https:\/\/doi.org\/10.1007\/ BFb0035176 Rainer Gawlick, Nancy A. Lynch, and Nir Shavit. 1992. Concurrent Timestamping Made Simple. In Theory of Computing and Systems, ISTCS'92, Israel Symposium, Haifa, Israel, May 1992 (Lecture Notes in Computer Science, Vol. 601), Danny Dolev, Zvi Galil, and Michael Rodeh (Eds.). Springer, 171--183. https:\/\/doi.org\/10.1007\/ BFb0035176"},{"volume-title":"Algorithms for Concurrent Systems","author":"Guerraoui Rachid","key":"e_1_3_2_2_19_1","unstructured":"Rachid Guerraoui and Petr Kuznetsov . 2018. Algorithms for Concurrent Systems . EPFL press . Rachid Guerraoui and Petr Kuznetsov. 2018. Algorithms for Concurrent Systems. EPFL press."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0042-0"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559904"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_2_23_1","volume-title":"7th International Workshop, WDAG '93, Lausanne, Switzerland, September 27--29, 1993, Proceedings (Lecture Notes in Computer Science","volume":"25","author":"Hoepman Jaap-Henk","year":"1993","unstructured":"Jaap-Henk Hoepman and John Tromp . 1993 . Binary Snapshots. In Distributed Algorithms , 7th International Workshop, WDAG '93, Lausanne, Switzerland, September 27--29, 1993, Proceedings (Lecture Notes in Computer Science , Vol. 725), Andr\u00e9 Schiper (Ed.). Springer, 18-- 25 . https:\/\/doi.org\/10.1007\/3--540--57271--6_24 Jaap-Henk Hoepman and John Tromp. 1993. Binary Snapshots. In Distributed Algorithms, 7th International Workshop, WDAG '93, Lausanne, Switzerland, September 27--29, 1993, Proceedings (Lecture Notes in Computer Science, Vol. 725), Andr\u00e9 Schiper (Ed.). Springer, 18--25. https:\/\/doi.org\/10.1007\/3--540--57271--6_24"},{"key":"e_1_3_2_2_24_1","volume-title":"8th International Workshop, WDAG '94, Terschelling, The Netherlands, September 29 - October 1, 1994, Proceedings (Lecture Notes in Computer Science","volume":"140","author":"Inoue Michiko","year":"1994","unstructured":"Michiko Inoue and Wei Chen . 1994 . Linear-Time Snapshot Using Multi-writer Multi-reader Registers. In Distributed Algorithms , 8th International Workshop, WDAG '94, Terschelling, The Netherlands, September 29 - October 1, 1994, Proceedings (Lecture Notes in Computer Science , Vol. 857), Gerard Tel and Paul M. B. Vit\u00e1nyi (Eds.). Springer, 130-- 140 . https:\/\/doi.org\/10.1007\/BFb0020429 Michiko Inoue and Wei Chen. 1994. Linear-Time Snapshot Using Multi-writer Multi-reader Registers. In Distributed Algorithms, 8th International Workshop, WDAG '94, Terschelling, The Netherlands, September 29 - October 1, 1994, Proceedings (Lecture Notes in Computer Science, Vol. 857), Gerard Tel and Paul M. B. Vit\u00e1nyi (Eds.). Springer, 130--140. https:\/\/doi.org\/10.1007\/BFb0020429"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"crossref","unstructured":"A. Israeli A. Shaham and A. Shirazi. 1995. Linear-time snapshot implementations in unbalanced systems. Mathematical systems theory 28 5 (01 Sep 1995) 469--486. https:\/\/doi.org\/10.1007\/BF01185868  A. Israeli A. Shaham and A. Shirazi. 1995. Linear-time snapshot implementations in unbalanced systems. Mathematical systems theory 28 5 (01 Sep 1995) 469--486. https:\/\/doi.org\/10.1007\/BF01185868","DOI":"10.1007\/BF01185868"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571875"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060697"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317299"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.296315"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357198"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00412-6"},{"key":"e_1_3_2_2_32_1","first-page":"6","article-title":"Converting Lamport's Regular Register to Atomic","volume":"28","author":"Vidyasankar K.","year":"1988","unstructured":"K. Vidyasankar . 1988 . Converting Lamport's Regular Register to Atomic Register. Inf. Process. Lett. 28 , 6 (Aug. 1988), 287--290. https:\/\/doi.org\/10.1016\/0020-0190(88) 90175--5 K. Vidyasankar. 1988. Converting Lamport's Regular Register to Atomic Register. Inf. Process. Lett. 28, 6 (Aug. 1988), 287--290. https:\/\/doi.org\/10.1016\/0020-0190(88) 90175--5","journal-title":"Register. Inf. Process. Lett."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441602"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897565"},{"key":"e_1_3_2_2_36_1","volume-title":"19th International Conference on Principles of Distributed Systems, OPODIS 2015","volume":"16","author":"Zhu Leqi","year":"2015","unstructured":"Leqi Zhu and Faith Ellen . 2015 . Atomic Snapshots from Small Registers . In 19th International Conference on Principles of Distributed Systems, OPODIS 2015 , December 14 --17 , 2015, Rennes, France (LIPIcs, Vol. 46), Emmanuelle Anceaume, Christian Cachin, and Maria Gradinariu Potop-Butucaru (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1--17: 16 . https:\/\/doi.org\/10.4230\/LIPIcs. OPODIS.2015.17 Leqi Zhu and Faith Ellen. 2015. Atomic Snapshots from Small Registers. In 19th International Conference on Principles of Distributed Systems, OPODIS 2015, December 14--17, 2015, Rennes, France (LIPIcs, Vol. 46), Emmanuelle Anceaume, Christian Cachin, and Maria Gradinariu Potop-Butucaru (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1--17:16. https:\/\/doi.org\/10.4230\/LIPIcs. OPODIS.2015.17"}],"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.3467916","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467916","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.3467916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":35,"alternative-id":["10.1145\/3465084.3467916","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467916","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"}}]}}