Woelfel, PhilippBashari, Benyamin2021-10-202021-10-202021-10-19Bashari, B. (2021). An Efficient Adaptive Partial Snapshot Implementation (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.http://hdl.handle.net/1880/114065In an asynchronous shared-memory system with n processes, the single-writer snapshot type provides consistent views of an array A of n components, each of which can be updated by one of the processes. Formally, a process p can call Update(v) to write v into A[p], and call Scan() to obtain a view of A. Inherently, under realistic assumptions on the base objects’ size, the specification of this type leads to a lower bound of Ω(n) steps for method Scan(). In some cases, it suffices for a process to take a snapshot of k (1 ≤ k ≤ n) components of A, and thus, taking Ω(n) steps to obtain that snapshot is inefficient when k is small. In this thesis, we provide an implementation of the single-writer adaptive partial snapshot type, which allows a process to take a partial snapshot of k components in O(k log n) steps. We define a new version of Scan() that does not return anything and its behavior is defined in terms of another operation Observe(). An Observe(i) operation by process p returns the value that A[i] had at the point in time of p’s preceding Scan(). We implement a single-writer adaptive partial snapshot object from read-write registers, fetch-and-increment objects, and compare-and-swap objects, such that the step complexity of method Scan() is O(1) and that of methods Update() and Observe() is O(log n).engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. 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.Shared MemoryConcurrencySnapshot ObjectPredecessor ObjectComputer Sciencemaster thesis10.11575/PRISM/39355