Strongly Linearizable Implementations of Fundamental Primitives

Simple item page
dc.contributor.advisorWoelfel, Philipp
dc.contributor.authorOvens, Sean
dc.contributor.committeememberWoelfel, Philipp
dc.contributor.committeememberCockett, J. Robin B.
dc.contributor.committeememberHendler, Danny
dc.date2019-11
dc.date.accessioned2019-08-21T18:00:33Z
dc.date.available2019-08-21T18:00:33Z
dc.date.issued2019-08-20
dc.description.abstractLinearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown [1] that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model [1]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel [2]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [3], which, as we show, is not strongly linearizable. Aspnes and Herlihy [4] identified a wide class types that have wait-free linearizable implementations from atomic registers. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing a wait-free linearizable snapshot object. Replacing that snapshot object with our lock-free strongly linearizable one, we prove that all types in this class have a lock-free strongly linearizable implementation from atomic registers.en_US
dc.identifier.citationOvens, S. (2019). Strongly Linearizable Implementations of Fundamental Primitives (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/36841
dc.identifier.urihttp://hdl.handle.net/1880/110755
dc.language.isoengen_US
dc.publisher.facultyScienceen_US
dc.publisher.institutionUniversity of Calgaryen
dc.rightsUniversity 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.subjectDistributed Algorithmsen_US
dc.subjectShared Memoryen_US
dc.subjectStrong Linearizabilityen_US
dc.subject.classificationComputer Scienceen_US
dc.titleStrongly Linearizable Implementations of Fundamental Primitivesen_US
dc.typemaster thesisen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorUniversity of Calgaryen_US
thesis.degree.nameMaster of Science (MSc)en_US
ucalgary.item.requestcopytrueen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2019_ovens_sean.pdf
Size:
872.94 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations