[{"date_published":"2020-07-31T00:00:00Z","date_created":"2020-09-13T22:01:17Z","title":"Long-lived snapshots with polylogarithmic amortized step complexity","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://hal.archives-ouvertes.fr/hal-02860087/document"}],"publication_identifier":{"isbn":["9781450375825"]},"year":"2020","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, 31–40. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3382734.3406005\">https://doi.org/10.1145/3382734.3406005</a>.","ista":"Baig MA, Hendler D, Milani A, Travers C. 2020. Long-lived snapshots with polylogarithmic amortized step complexity. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 31–40.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived snapshots with polylogarithmic amortized step complexity. In: <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2020:31-40. doi:<a href=\"https://doi.org/10.1145/3382734.3406005\">10.1145/3382734.3406005</a>","apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2020). Long-lived snapshots with polylogarithmic amortized step complexity. In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i> (pp. 31–40). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3382734.3406005\">https://doi.org/10.1145/3382734.3406005</a>","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived snapshots with polylogarithmic amortized step complexity,” in <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2020, pp. 31–40.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 31–40.","mla":"Baig, Mirza Ahad, et al. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2020, pp. 31–40, doi:<a href=\"https://doi.org/10.1145/3382734.3406005\">10.1145/3382734.3406005</a>."},"day":"31","abstract":[{"text":"We present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads and writes only, that has sub-linear amortized step complexity in executions of arbitrary length. The key to our construction is a novel implementation of a 2-component max array object which may be of independent interest.","lang":"eng"}],"_id":"8382","language":[{"iso":"eng"}],"external_id":{"isi":["001436693500004"]},"type":"conference","quality_controlled":"1","publication_status":"published","conference":{"end_date":"2020-08-07","location":"Virtual, Italy","name":"PODC: Principles of Distributed Computing","start_date":"2020-08-03"},"scopus_import":"1","article_processing_charge":"No","publisher":"Association for Computing Machinery","status":"public","page":"31-40","publication":"Proceedings of the 39th Symposium on Principles of Distributed Computing","date_updated":"2025-09-10T10:25:23Z","author":[{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","last_name":"Baig","full_name":"Baig, Mirza Ahad"},{"last_name":"Hendler","full_name":"Hendler, Danny","first_name":"Danny"},{"full_name":"Milani, Alessia","last_name":"Milani","first_name":"Alessia"},{"full_name":"Travers, Corentin","last_name":"Travers","first_name":"Corentin"}],"isi":1,"month":"07","oa":1,"doi":"10.1145/3382734.3406005"},{"day":"31","citation":{"short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 54–56.","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Brief Announcement: Why Extension-Based Proofs Fail,” in <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2020, pp. 54–56.","mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Why Extension-Based Proofs Fail.” <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2020, pp. 54–56, doi:<a href=\"https://doi.org/10.1145/3382734.3405743\">10.1145/3382734.3405743</a>.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2020). Brief Announcement: Why Extension-Based Proofs Fail. In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i> (pp. 54–56). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3382734.3405743\">https://doi.org/10.1145/3382734.3405743</a>","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2020. Brief Announcement: Why Extension-Based Proofs Fail. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 54–56.","ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Brief Announcement: Why Extension-Based Proofs Fail. In: <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2020:54-56. doi:<a href=\"https://doi.org/10.1145/3382734.3405743\">10.1145/3382734.3405743</a>","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Brief Announcement: Why Extension-Based Proofs Fail.” In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, 54–56. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3382734.3405743\">https://doi.org/10.1145/3382734.3405743</a>."},"external_id":{"isi":["001436693500007"]},"_id":"8383","abstract":[{"lang":"eng","text":"We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power."}],"language":[{"iso":"eng"}],"conference":{"location":"Virtual, Italy","end_date":"2020-08-07","start_date":"2020-08-03","name":"PODC: Principles of Distributed Computing"},"quality_controlled":"1","publication_status":"published","type":"conference","title":"Brief Announcement: Why Extension-Based Proofs Fail","date_created":"2020-09-13T22:01:18Z","date_published":"2020-07-31T00:00:00Z","oa_version":"None","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2020","publication_identifier":{"isbn":["9781450375825"]},"author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Aspnes","full_name":"Aspnes, James","first_name":"James"},{"first_name":"Faith","full_name":"Ellen, Faith","last_name":"Ellen"},{"first_name":"Rati","full_name":"Gelashvili, Rati","last_name":"Gelashvili"},{"first_name":"Leqi","last_name":"Zhu","full_name":"Zhu, Leqi"}],"date_updated":"2025-09-10T10:26:32Z","publication":"Proceedings of the 39th Symposium on Principles of Distributed Computing","department":[{"_id":"DaAl"}],"isi":1,"month":"07","doi":"10.1145/3382734.3405743","scopus_import":"1","article_processing_charge":"No","page":"54-56","status":"public","publisher":"Association for Computing Machinery"}]