An Efficient Adaptive Partial Snapshot Implementation

Bashari, Benyamin

An Efficient Adaptive Partial Snapshot Implementation

dc.contributor.advisor	Woelfel, Philipp
dc.contributor.author	Bashari, Benyamin
dc.contributor.committeemember	Woelfel, Philipp
dc.contributor.committeemember	Ruppert, Eric
dc.contributor.committeemember	Jacobson, Michael
dc.date	2022-06
dc.date.accessioned	2021-10-20T20:25:27Z
dc.date.available	2021-10-20T20:25:27Z
dc.date.issued	2021-10-19
dc.description.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).	en_US
dc.identifier.citation	Bashari, B. (2021). An Efficient Adaptive Partial Snapshot Implementation (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.	en_US
dc.identifier.doi	http://dx.doi.org/10.11575/PRISM/39355
dc.identifier.uri	http://hdl.handle.net/1880/114065
dc.language.iso	eng	en_US
dc.publisher.faculty	Science	en_US
dc.publisher.institution	University of Calgary	en
dc.rights	University 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.	en_US
dc.subject	Shared Memory	en_US
dc.subject	Concurrency	en_US
dc.subject	Snapshot Object	en_US
dc.subject	Predecessor Object	en_US
dc.subject.classification	Computer Science	en_US
dc.title	An Efficient Adaptive Partial Snapshot Implementation	en_US
dc.type	master thesis	en_US
thesis.degree.discipline	Computer Science	en_US
thesis.degree.grantor	University of Calgary	en_US
thesis.degree.name	Master of Science (MSc)	en_US
ucalgary.item.requestcopy	true	en_US