Non-Blocking Data Structures Handling Multiple Changes Atomically

Simple item page
dc.contributor.advisorRuppert, Eric
dc.creatorShafiei, Niloufar
dc.date.accessioned2015-12-16T19:19:40Z
dc.date.available2015-12-16T19:19:40Z
dc.date.copyright2015-07-03
dc.date.issued2015-12-16
dc.date.updated2015-12-16T19:19:40Z
dc.degree.disciplineComputer Science
dc.degree.levelDoctoral
dc.degree.namePhD - Doctor of Philosophy
dc.description.abstractHere, we propose a new approach to design non-blocking algorithms that can apply multiple changes to a shared data structure atomically using Compare&Swap (CAS) instructions. We applied our approach to two data structures, doubly-linked lists and Patricia tries. In our implementations, only update operations perform CAS instructions; operations other than updates perform only reads of shared memory. Our doubly-linked list implements a novel specification that is designed to make it easy to use as a black box in a concurrent setting. In our doubly-linked list implementation, each process accesses the list via a cursor, which is an object in the process's local memory that is located at an item in the list. Our specification describes how updates affect cursors and how a process gets feedback about other processes' updates at the location of its cursor. We provide a detailed proof of correctness for our list implementation. We also give an amortized analysis for our list implementation, which is the first upper bound on amortized time complexity that has been proved for a concurrent doubly-linked list. In addition, we evaluate our list algorithms on a multi-core system empirically to show that they are scalable in practice. Our non-blocking Patricia trie implementation stores a set of keys, represented as bit strings, and allows processes to concurrently insert, delete and find keys. In addition, our implementation supports the replace operation, which deletes a key from the trie and adds a new key to the trie simultaneously. Since the correctness proof of our trie is similar to the correctness proof of our list implementation, we only provide a sketch of a correctness proof of our trie implementation here. We empirically evaluate our trie and compare our trie to some existing set implementations. Our empirical results show that our Patricia trie implementation consistently performs well under different scenarios.
dc.identifier.urihttp://hdl.handle.net/10315/30672
dc.language.isoen
dc.rightsAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.
dc.subjectComputer science
dc.subjectEngineering
dc.subject.keywordscomputer science
dc.subject.keywordsshared memory
dc.subject.keywordsdata structure
dc.subject.keywordsshared data structure
dc.subject.keywordsconcurrent data structure
dc.subject.keywordsconcurrency
dc.subject.keywordslist
dc.subject.keywordslinked list
dc.subject.keywordsdoubly-linked list
dc.subject.keywordsPatricia trie
dc.subject.keywordstree
dc.subject.keywordsbinary tree
dc.subject.keywordsnon-blocking
dc.subject.keywordswait-free
dc.subject.keywordslock-free
dc.subject.keywordsdistributed computing
dc.subject.keywordsdistributed system
dc.subject.keywordscomplexity
dc.subject.keywordsanalysis
dc.subject.keywordsamortized analysis
dc.subject.keywordscursor
dc.subject.keywordsdescriptor
dc.subject.keywordsinfo object
dc.subject.keywordsdescriptor object
dc.subject.keywordsnon-blocking data structure
dc.subject.keywordsempirical evaluation
dc.subject.keywordsexperiments
dc.subject.keywordscorrectness proof
dc.subject.keywordsproof
dc.subject.keywordspotential function
dc.subject.keywordsgeneral approach
dc.subject.keywordsmultiple changes
dc.subject.keywordslinearizable
dc.subject.keywordslinearizability
dc.subject.keywordscorrectness condition
dc.subject.keywordsperformance
dc.subject.keywordsabstract data structure
dc.subject.keywordstrie
dc.subject.keywordsnovel sequential specification
dc.subject.keywordssequential specification
dc.subject.keywordsblack box
dc.subject.keywordsmodular approach
dc.subject.keywordsmodular
dc.subject.keywordssequence
dc.subject.keywordssequence of items
dc.subject.keywordsreplace operation
dc.subject.keywordspoint contention
dc.subject.keywordsquadtree
dc.subject.keywordsGIS
dc.subject.keywordsGeographic Information System
dc.subject.keywordsgeneral technique
dc.subject.keywordshelp
dc.subject.keywordshelping mechanism
dc.subject.keywordsrobust
dc.subject.keywordsrobust cursor
dc.subject.keywordssorted
dc.subject.keywordssorted list
dc.subject.keywordsordered list
dc.subject.keywordsactive cursor
dc.subject.keywordsmulti-core system
dc.subject.keywordsmulti-core
dc.subject.keywordsmulticore machine
dc.subject.keywordsuniformly distributed keys
dc.subject.keywordsnon-uniformly distributed keys
dc.subject.keywordsmove
dc.subject.keywordsmove operation
dc.subject.keywordsupdate operation
dc.subject.keywordsmove cursor
dc.subject.keywordsalgorithm
dc.subject.keywordsdistributed algorithm
dc.subject.keywordsimplementation
dc.subject.keywordsnon-blocking implementation
dc.titleNon-Blocking Data Structures Handling Multiple Changes Atomically
dc.typeElectronic Thesis or Dissertation

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Shafiei_Niloufar_2015_PhD.pdf
Size:
2.03 MB
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.