---
res:
  bibo_abstract:
  - In order to guarantee that each method of a data structure updates the logical
    state exactly once, al-most all non-blocking implementations employ Compare-And-Swap
    (CAS) based synchronization. For FIFO  queue  implementations  this  translates  into  concurrent  enqueue  or  dequeue  methods
    competing among themselves to update the same variable, the tail or the head,
    respectively, leading to high contention and poor scalability. Recent non-blocking
    queue implementations try to alleviate high contentionby increasing the number
    of contention points, all the while using CAS-based synchronization. Furthermore,
    obtaining a wait-free implementation with competition is achieved by additional
    synchronization which leads to further degradation of performance.In this paper
    we formalize the notion of competitiveness of a synchronizing statement which
    can beused as a measure for the scalability of concurrent implementations.  We
    present a new queue implementation, the Speculative Pairing (SP) queue, which,
    as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead
    of CAS. We prove that the SP queue is linearizable and lock-free.We also show
    that replacing CAS with FAI leads to wait-freedom for dequeue methods without
    an adverse effect on performance.  In fact, our experiments suggest that the SP
    queue can perform and scale better than the state-of-the-art queue implementations.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Thomas A
      foaf_name: Henzinger, Thomas A
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
    orcid: 0000−0002−2985−7724
  - foaf_Person:
      foaf_givenName: Hannes
      foaf_name: Payer, Hannes
      foaf_surname: Payer
  - foaf_Person:
      foaf_givenName: Ali
      foaf_name: Sezgin, Ali
      foaf_surname: Sezgin
      foaf_workInfoHomepage: http://www.librecat.org/personId=4C7638DA-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.15479/AT:IST-2013-124-v1-1
  dct_date: 2013^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2664-1690
  dct_language: eng
  dct_publisher: IST Austria@
  dct_title: Replacing competition with cooperation to achieve scalable lock-free
    FIFO queues @
...