A Wait-free Queue with Poly-logarithmic Worst-case Step Complexity

Simple item page
dc.contributor.advisorRuppert, Eric
dc.contributor.authorNaderibeni, Hossein
dc.date.accessioned2023-03-28T21:15:14Z
dc.date.available2023-03-28T21:15:14Z
dc.date.copyright2022-11-09
dc.date.issued2023-03-28
dc.date.updated2023-03-28T21:15:14Z
dc.degree.disciplineComputer Science
dc.degree.levelMaster's
dc.degree.nameMSc - Master of Science
dc.description.abstractIn this work, we introduce a novel linearizable wait-free queue implementation. Linearizability and lock-freedom are standard requirements for designing shared data structures. To the best of our knowledge, all of the existing linearizable lock-free queues in the literature have a common problem in their worst case, called the CAS Retry Problem. We show that our algorithm avoids this problem with the helping mechanism which we use and has a worst-case running time better than prior lock-free queues. The amortized number of steps for an Enqueue or Dequeue in our algorithm is O(log^2 p + log q), where p is the number of processes and q is the size of the queue when the operation is linearized.
dc.identifier.urihttp://hdl.handle.net/10315/40975
dc.languageen
dc.rightsAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.
dc.subjectComputer science
dc.subject.keywordsDistributed computing
dc.subject.keywordsConcurrent algorithms
dc.subject.keywordsShared data structures
dc.subject.keywordsWait-free queues
dc.subject.keywordsLinearizable
dc.subject.keywordsCAS retry problem
dc.subject.keywordsPolylogarithmic step complexity
dc.titleA Wait-free Queue with Poly-logarithmic Worst-case Step Complexity
dc.typeElectronic Thesis or Dissertation

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
A_Wait_free_Queue_with_Poly_logarithmic_Step_Complexity-2.pdf
Size:
1.14 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
license.txt
Size:
1.87 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
YorkU_ETDlicense.txt
Size:
3.39 KB
Format:
Plain Text
Description:
Download

Collections

Computer Science

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