Bashari, BenyaminWoelfel, Philipp2021-06-092021-06-092021-06-06Bashari, 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.3467939http://hdl.handle.net/1880/113478The 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).engUnless otherwise indicated, this material is protected by copyright and has been made available with authorization from the copyright owner. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.https://creativecommons.org/licenses/by/4.0Shared MemoryConcurrencyPredecessor ObjectAsynchronySnapshot Objectconference paperRGPIN/2019-0485210.1145/3465084.3467939