Long-lived snapshots with polylogarithmic amortized step complexity

M.A. Baig, D. Hendler, A. Milani, C. Travers, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, ACM, 2020, pp. 31–40.


Conference Paper | Published | English

Scopus indexed
Author
Baig, Mirza AhadIST Austria; 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
Page
31-40
Conference
PODC: Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2020-08-03 – 2020-08-07
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. ACM; 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: ACM. 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. ACM, 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, ACM, 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
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search