Long-lived snapshots with polylogarithmic amortized step complexity
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.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Baig, Mirza AhadISTA;
Hendler, Danny;
Milani, Alessia;
Travers, Corentin
Abstract
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.
Publishing Year
Date Published
2020-07-31
Proceedings Title
Proceedings of the 39th Symposium on Principles of Distributed Computing
Publisher
Association for Computing Machinery
Page
31-40
Conference
PODC: Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2020-08-03 – 2020-08-07
ISBN
IST-REx-ID
Cite this
Baig MA, Hendler D, Milani A, Travers C. Long-lived snapshots with polylogarithmic amortized step complexity. In: Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2020:31-40. doi:10.1145/3382734.3406005
Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2020). Long-lived snapshots with polylogarithmic amortized step complexity. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 31–40). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3382734.3406005
Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” In Proceedings of the 39th Symposium on Principles of Distributed Computing, 31–40. Association for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3406005.
M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived snapshots with polylogarithmic amortized step complexity,” in Proceedings of the 39th Symposium on Principles of Distributed Computing, Virtual, Italy, 2020, pp. 31–40.
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.
Baig, Mirza Ahad, et al. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 31–40, doi:10.1145/3382734.3406005.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar
ISBN Search