Adaptive Partial Snapshots with Logarithmic Step Complexity

Simple item page
dc.contributor.authorBashari, Benyamin
dc.contributor.authorWoelfel, Philipp
dc.date.accessioned2021-06-09T17:35:27Z
dc.date.available2021-06-09T17:35:27Z
dc.date.issued2021-06-06
dc.description.abstractThe 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).en_US
dc.description.grantingagencyNatural Sciences and Engineering Research Council (NSERC)en_US
dc.identifier.citationBashari, 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.3467939en_US
dc.identifier.doi10.1145/3465084.3467939en_US
dc.identifier.grantnumberRGPIN/2019-04852en_US
dc.identifier.urihttp://hdl.handle.net/1880/113478
dc.identifier.urihttps://dx.doi.org/10.11575/PRISM/38911
dc.language.isoengen_US
dc.publisher.departmentComputer Scienceen_US
dc.publisher.facultyScienceen_US
dc.publisher.hasversionacceptedVersionen_US
dc.publisher.institutionUniversity of Calgaryen_US
dc.rightsUnless 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.en_US
dc.rights.urihttps://creativecommons.org/licenses/by/4.0en_US
dc.subjectShared Memoryen_US
dc.subjectConcurrencyen_US
dc.subjectPredecessor Objecten_US
dc.subjectAsynchronyen_US
dc.subjectSnapshot Objecten_US
dc.titleAdaptive Partial Snapshots with Logarithmic Step Complexityen_US
dc.typeconference paperen_US
ucalgary.item.requestcopytrueen_US
ucalgary.scholar.levelGraduate Studenten_US
ucalgary.scholar.levelFaculty Memberen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Adaptive-Partial-Snapshot.pdf
Size:
761.72 KB
Format:
Adobe Portable Document Format
Description:
Main Article
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.92 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Science Research & Publications