Characterizing Implementations that Preserve Properties of Concurrent Randomized Algorithms

Simple item page
dc.contributor.advisorRuppert, Eric
dc.creatorRady, Amgad Sadek
dc.date.accessioned2018-05-28T12:53:44Z
dc.date.available2018-05-28T12:53:44Z
dc.date.copyright2017-12-04
dc.date.issued2018-05-28
dc.date.updated2018-05-28T12:53:44Z
dc.degree.disciplineComputer Science
dc.degree.levelMaster's
dc.degree.nameMSc - Master of Science
dc.description.abstractWe show that correctness criteria of concurrent algorithms are mathematically equivalent to the existence of so-called simulations between implementations of the algorithms in a well-known framework (that of input/output automata) and simple canonical automata. This equivalence allows us to frame our proofs of correctness in a language much more amenable to machine-checking than conventional proofs. We give the first demonstration that when strongly linearizable implementations of randomized concurrent algorithms are utilized, then the distributions of a well-defined class of random variables are preserved under object substitution by non-concurrent implementations of the same algorithms. We also consider weaker conditions than strong linearizability under which implementations are still correct in the presence of randomization.
dc.identifier.urihttp://hdl.handle.net/10315/34539
dc.language.isoen
dc.rightsAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.
dc.subjectComputer science
dc.subject.keywordsComputer science
dc.subject.keywordsDistributed computing
dc.subject.keywordsVerification
dc.subject.keywordsRandomized algorithms
dc.subject.keywordsSimulations
dc.subject.keywordsLinearizability
dc.subject.keywordsStrong linearizability
dc.titleCharacterizing Implementations that Preserve Properties of Concurrent Randomized Algorithms
dc.typeElectronic Thesis or Dissertation

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Rady_Amgad_S_2017_Masters.pdf
Size:
617.02 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
license.txt
Size:
1.83 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
YorkU_ETDlicense.txt
Size:
3.38 KB
Format:
Plain Text
Description:
Download

Collections

Computer Science and Engineering

All items in the YorkSpace institutional repository are protected by copyright, with all rights reserved except where explicitly noted.