Adaptive Partial Snapshots with Logarithmic Step Complexity
Date
2021-06-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a Scan() operation returns a linearizable snapshot of the entire array. Under realistic assumptions, where hardware registers do not have the capacity to store many array entries, this inherently leads to a step complexity of Ω(n). In this paper, we consider an alternative version of the snapshot type, where a Scan() operation stores a consistent snapshot of all n memory locations, but does not return anything. Instead, a process can later observe the value of any component of that snapshot using a separate Observe() operation. This allows us to implement the type from fetch-and-increment and compare-and-swap objects, such that Scan() operations have constant step complexity and Update() and Observe() operations have step complexity O(logn).
Description
Keywords
Shared Memory, Concurrency, Predecessor Object, Asynchrony, Snapshot Object
Citation
Bashari, B. & Woelfel, P. (2021). An Efficient Adaptive Partial Snapshot Implementation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC ’21), July 26–30, 2021, Virtual Event, Italy. ACM, New York, NY, USA, 11 pages. https://doi.org/10.1145/ 3465084.3467939