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

In 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 dc:creator

• Naderibeni, Hossein

Advisor dc:contributor.advisor

• Ruppert, Eric

• Computer science

Statement dc:rights

• Author owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.

Language dc:language

en

Handle dc:identifier.uri

http://hdl.handle.net/10315/40975

OAI identifier oai:identifier

oai:yorkspace.library.yorku.ca:10315/40975