Ruppert, EricNaderibeni, Hossein2023-03-282023-03-282022-11-092023-03-28http://hdl.handle.net/10315/40975In 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.Author owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.Computer scienceElectronic Thesis or Dissertation2023-03-28Distributed computingConcurrent algorithmsShared data structuresWait-free queuesLinearizableCAS retry problemPolylogarithmic step complexity