An Efficient Adaptive Partial Snapshot Implementation
Date
2021-10-19
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In 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).
Description
Keywords
Shared Memory, Concurrency, Snapshot Object, Predecessor Object
Citation
Bashari, B. (2021). An Efficient Adaptive Partial Snapshot Implementation (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.