Ruppert, Eric2015-12-162015-12-162015-07-032015-12-16http://hdl.handle.net/10315/30672Here, 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.enAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.Computer scienceEngineeringElectronic Thesis or Dissertation2015-12-16computer scienceshared memorydata structureshared data structureconcurrent data structureconcurrencylistlinked listdoubly-linked listPatricia trietreebinary treenon-blockingwait-freelock-freedistributed computingdistributed systemcomplexityanalysisamortized analysiscursordescriptorinfo objectdescriptor objectnon-blocking data structureempirical evaluationexperimentscorrectness proofproofpotential functiongeneral approachmultiple changeslinearizablelinearizabilitycorrectness conditionperformanceabstract data structuretrienovel sequential specificationsequential specificationblack boxmodular approachmodularsequencesequence of itemsreplace operationpoint contentionquadtreeGISGeographic Information Systemgeneral techniquehelphelping mechanismrobustrobust cursorsortedsorted listordered listactive cursormulti-core systemmulti-coremulticore machineuniformly distributed keysnon-uniformly distributed keysmovemove operationupdate operationmove cursoralgorithmdistributed algorithmimplementationnon-blocking implementation