Pith. sign in

REVIEW 3 major objections 3 minor 24 references

A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper presents SCQ, a bounded lock-free MPMC FIFO queue that uses fetch-and-add on its most contended hot spots, avoids ABA problems, needs no safe memory reclamation, and is portable to any architecture with single-width CAS.

desk verdict This is a genuinely new lock-free bounded queue design with solid benchmarks, but the correctness proof is a handwave that needs to be redone. read the letter →

arxiv 1908.04511 v1 pith:O3QYIJD3 submitted 2019-08-13 cs.DC

Ruslan Nikolaev This is my paper · ORCID
classification cs.DC
keywords lock-freequeueMPMCFIFOfetch-and-addringbufferABAsafetymemoryefficiencylinearizabilitySCQ
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that a concurrent FIFO queue, one that many producers and many consumers can use at once, can be both lock-free and scalable without paying the usual memory costs. Its design, SCQ, is a bounded ring buffer that uses fetch-and-add (FAA) rather than compare-and-set (CAS) on the contended head and tail pointers, which makes it fast under high contention. Because it stores indices instead of pointers and recycles them through two internal queues, SCQ needs no external memory allocator and no safe memory reclamation, and it is immune to the ABA problem. If the claims hold, SCQ would be a drop-in queue for fixed-size data pools and for architectures without double-width CAS, such as PowerPC, MIPS, and RISC-V. The paper also gives an unbounded variant, LSCQ, that chains SCQ buffers together and is more memory-efficient than the prior LCRQ design.

What carries the argument

The algorithm's central object is a circular buffer of 2n entries, each carrying a cycle number, an index into a separate data array, and a one-bit safety flag. Head and Tail are monotonically increasing counters updated by FAA, so both positions grow as position plus cycle times n; ABA is avoided because entries are matched to cycles rather than recycled pointers. A dequeuer that arrives early clears the safety bit with a CAS, or consumes the entry with an atomic OR when cycles match, and an enqueuer is allowed to write only when the slot is free, the cycle is old enough, and either the safety bit is set or Head has caught up. A Cache_Remap function spreads adjacent entries over different cache lines to reduce false sharing. The livelock barrier is a shared Threshold counter set to 3n−1 by each successful enqueue and decremented by each failed dequeue, bounding how far dequeuers can run ahead of the last inserted entry.

What would settle it

Set the queue capacity to n=2 and run k=3 threads in a tight loop of enqueue and dequeue with delays chosen to force one thread to be preempted mid-operation; if there is an execution in which after some finite point no thread ever completes another operation, the lock-freedom guarantee fails when k>n. Alternatively, instrument the algorithm to count consecutive failed dequeue attempts, threshold decrements, between successful enqueues: under the paper's assumptions a value above 3n−1 would contradict the livelock-prevention argument.

Watch

Extended reading notes

Core claim

The paper's central claim is that SCQ is a standalone, linearizable, lock-free MPMC FIFO queue that is scalable, memory-efficient, and ABA-safe while relying only on single-width atomic operations. Enqueue and dequeue advance the head and tail counters with fetch-and-add, and dequeue marks a consumed slot with an atomic OR instead of a CAS; a shared threshold counter, reset by every successful enqueue and decremented by failed dequeues, stops the livelock that made earlier FAA-based ring buffers unusable alone. Entries hold an index into a separate data array rather than a pointer, and a pair of internal queues (fq and aq) recycle those indices, which is why no memory allocator or safe memory reclamation is needed. The paper argues linearizability by analogy with CRQ and proves lock-freedom under the assumption that the number of threads k never exceeds the queue size n, then reports benchmarks on x86-64 and PowerPC showing throughput competitive with LCRQ and WFQUEUE while consuming a small fixed buffer where LCRQ can consume hundreds of megabytes.

Load-bearing premise

The load-bearing premise is that the number of concurrent threads k never exceeds the queue size n (k ≤ n), because the threshold value 3n−1 that prevents livelock is derived from that bound; with more active threads than slots, dequeuers could keep invalidating slots and the lock-freedom proof no longer applies.

Editorial extensions

If this is right

  • SCQ can be used as a lock-free queue in fixed-size data pools without an external memory allocator, since it recycles its own entries through the fq/aq pair.
  • Architectures without double-width CAS, such as PowerPC, MIPS, SPARC, and RISC-V, can implement SCQ directly, which prior high-performance designs like LCRQ could not.
  • Bounded SCQ eliminates the need for hazard pointers or other safe-memory-reclamation schemes in the common case, simplifying integration into kernels and embedded systems.
  • The unbounded LSCQ variant chains SCQ buffers and, according to the paper, uses less memory than LCRQ because SCQ does not prematurely finalize buffers due to livelocks.
  • On the reported benchmarks, SCQ and SCQP match or exceed the throughput of LCRQ and WFQUEUE on x86-64 and generally outperform them on PowerPC, while keeping memory usage at roughly 512KB to 1MB.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The threshold-counter idea is a generic pattern that could be transplanted to other FAA-based ring buffers to give them operation-wise lock-freedom without a fallback queue.
  • The same fq/aq indirection suggests an immediate application as a lock-free object pool or slab allocator, where the queue itself performs allocation and reclamation.
  • A stress test at k > n would show whether the queue degrades to merely practical or loses its guarantee; nothing in the paper's proof covers that regime.
  • If SCQ's memory advantage holds at large scale, it may be preferable to higher-peak-throughput queues in memory-constrained and latency-critical systems.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper presents SCQ, a bounded lock-free MPMC FIFO queue design that uses fetch-and-add (FAA) on the Head and Tail pointers, a threshold mechanism to prevent livelocks, and a bounded ring buffer with cycle arithmetic to avoid the ABA problem without double-width CAS. The design is extended to an unbounded queue (LSCQ) by chaining SCQ buffers. The paper claims that SCQ is scalable, memory-efficient, ABA-safe, does not require external memory allocators or safe memory reclamation, and is portable across architectures without double-width CAS, including PowerPC. The authors provide a correctness section with an informal proof of lock-freedom, and they benchmark SCQ against M&S, CCQUEUE, LCRQ, and WFQUEUE on x86-64 and POWER8, reporting competitive performance and much lower memory usage than LCRQ.

Significance. If the correctness claims hold, SCQ is a practically valuable contribution: it offers a bounded lock-free queue with FAA-based scaling and no dependency on safe memory reclamation, which is important for fixed-size data pools and for architectures lacking double-width CAS. The memory-efficiency evidence (e.g., Figure 12b) is compelling, and the portability across x86-64 and POWER8 is demonstrated by benchmarks. The paper also provides a public implementation, which supports reproducibility. However, the central correctness proof, especially the linearizability argument, is not rigorous enough to support the strongest claims, and the lock-freedom proof contains gaps that need to be addressed.

major comments (3)
  1. [Section 6 (Correctness), first paragraph] The claim that "SCQ's linearizability follows from ... the corresponding CRQ linearizability derivations [19]" is not supported. CRQ's proof is for an algorithm over an unbounded array of slots with double-width CAS; SCQ's bounded 2n-slot ring with cycle arithmetic, the per-slot IsSafe bit, the Atomic_OR consumption step, the catchup procedure, and the Threshold-based empty return are all absent from that earlier proof. The paper needs to give explicit linearization points for dequeue (including the Threshold-triggered empty return and the catchup path) and for enqueue (including the case where the FAA in Line 13 reserves a slot whose CAS on Line 18 fails, and the thread retries with a later Tail value), and to prove the FIFO invariant that the order of linearized enqueues matches the order of values returned by dequeues. As written, the central correctness claim is not established.
  2. [Section 6, Theorem 2] The lock-freedom proof of Theorem 2 is a sketch rather than a proof. It does not account for all reasons the condition on Line 16 of Figure 8 can be false; for example, if Cycle(Ent) > Cycle(T), the enqueuer's Tail is stale, which is not covered by the two cases listed. The threshold argument in Section 5.1 is developed for the infinite-array queue of Figure 6 and then extended to SCQ with the sentence "the threshold value should now become (n−1+2n)=3n−1" without a derivation of the counting bound for SCQ's additional failure modes (e.g., CAS failures due to competing enqueuers, the interaction of IsSafe with Head, and the catchup path). The proof also does not handle the possibility that pending enqueuers reset Threshold at Line 21 after the threshold is depleted. A rigorous progress argument with explicit bounds on the number of failures is needed to support the lock-free claim.
  3. [Section 3 (Assumptions) and Section 6 (Theorem 2)] The entire progress proof relies on the assumption k ≤ n, stated in Section 3. The paper does not discuss what happens when this assumption is violated, and the threshold value 3n−1 is derived using the bound of at most n−1 concurrent dequeuers. Since the abstract and contributions present SCQ as a general lock-free queue, the dependence on k ≤ n must be stated as a formal condition in the main theorems and highlighted as a limitation; alternatively, the authors should extend the proof beyond this bound.
minor comments (3)
  1. [Throughout] The manuscript contains numerous typographical artifacts (e.g., "/f_inite", "/f_irst", "/f_lexible") that should be cleaned in the final version.
  2. [Section 5.4, Figure 10] The full-queue check allows Tail to run up to 3n slots ahead of Head, but no invariant is provided to justify the threshold increase from 3n−1 to 4n−1 beyond the informal statement in the text.
  3. [Section 5.3] The unbounded LSCQ extension is presented without a correctness argument; the paper should at least state which parts of the CRQ list-construction proof apply and which do not, given that SCQ cannot be finalized in the same way as CRQ.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: thresholds are derived from n and k ≤ n, and the CRQ citation is external, so the linearizability delegation is a proof gap, not a circular reduction.

full rationale

The paper's central quantitative parameters are not fitted inputs. The threshold values 2n−1 (infinite array), 3n−1 (SCQ), and 4n−1 (double-width SCQ) are derived from the queue size n and the stated assumption k ≤ n (Section 3), not from data, and no quantity that is 'predicted' is used to define the model. The FAA/CAS performance comparison and the queue benchmarks are external measurements with no fitted constants feeding back into the algorithm. The only citation-bearing correctness step is Section 6, where SCQ linearizability is said to 'follow from the arguments we make in Sections 5.1 and 5.2, as well as from the corresponding CRQ linearizability derivations [19]'; however, [19] is an external paper not authored by this paper's author, so this is not a self-citation chain. That delegation is a genuine proof gap, because SCQ's bounded ring, IsSafe bit, atomic-OR consumption, threshold, and catchup are not shown point-by-point to satisfy CRQ's proof, but a proof gap is not circularity: it does not make the claimed result equivalent to an input by construction. Lock-freedom is argued from the queue invariants and thresholds rather than assumed, and the reader's caveat about k ≤ n is an assumption sensitivity, not a circular fit.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central proof rests on a small set of domain assumptions: sequential consistency, the k ≤ n bound, non-wrapping counters, power-of-two size, and availability of atomic primitives. The most fragile is the k ≤ n bound, which fixes the threshold values. The reliance on CRQ's linearizability proof is an ad hoc assumption specific to this paper, since the algorithmic differences are not formally bridged.

assumptions (6)
  • domain assumption The system memory model is sequentially consistent for the purpose of correctness arguments.
    Section 3 states the algorithms are presented under sequential consistency, while implementations may use weaker models; the proof is therefore conditional on this memory model.
  • domain assumption The number of concurrent threads k does not exceed the maximum queue size n (k ≤ n).
    Section 3, 'Assumptions', explicitly assumes k≤n. This bound is used to derive the threshold value 3n−1; if violated, the livelock-avoidance proof breaks.
  • domain assumption Head and Tail counters never wrap around during a run.
    Section 3, 'ABA safety', assumes the counters will not wrap before exceeding the CPU word's largest value; this assumption underwrites the cycle-based ABA protection.
  • domain assumption The queue size n is a power of two in the implementation.
    Section 3 says 'must be power of 2 in our implementation', which allows the cycle/index decomposition via shifts and masking.
  • ad hoc to paper SCQ's linearizability follows from CRQ's linearizability proof by similarity.
    Section 6 states SCQ's linearizability is inherited from the CRQ derivations [19]. The differences (threshold, two queues, atomic OR instead of SWAP, no double-width CAS) are not formally bridged, so this is an unproven premise specific to this paper's proof strategy.
  • domain assumption Atomic operations used (FAA, SWAP, CAS, atomic OR) are available on target architectures.
    Sections 2 and 5 rely on these primitives; the portability claim depends on their availability, e.g., atomic OR on a word is assumed to be available.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue." pith.science (2026). https://pith.science/paper/O3QYIJD3

@misc{pith2026190804511,
  author       = {Pith},
  title        = {Pith review of: A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O3QYIJD3}},
  note         = {Machine review of arXiv:1908.04511}
}
read the original abstract

We present a new lock-free multiple-producer and multiple-consumer (MPMC) FIFO queue design which is scalable and, unlike existing high-performant queues, very memory efficient. Moreover, the design is ABA safe and does not require any external memory allocators or safe memory reclamation techniques, typically needed by other scalable designs. In fact, this queue itself can be leveraged for object allocation and reclamation, as in data pools. We use FAA (fetch-and-add), a specialized and more scalable than CAS (compare-and-set) instruction, on the most contended hot spots of the algorithm. However, unlike prior attempts with FAA, our queue is both lock-free and linearizable. We propose a general approach, SCQ, for bounded queues. This approach can easily be extended to support unbounded FIFO queues which can store an arbitrary number of elements. SCQ is portable across virtually all existing architectures and flexible enough for a wide variety of uses. We measure the performance of our algorithm on the x86-64 and PowerPC architectures. Our evaluation validates that our queue has exceptional memory efficiency compared to other algorithms and its performance is often comparable to, or exceeding that of state-of-the-art scalable algorithms.

Figures

Figures reproduced from arXiv: 1908.04511 by the authors.

Figure 1
Figure 1. FAA vs. CAS on 4x18 Xeon E7-8880. 1 int Tail = 0, Head = 0; // Queue’s tail and head 2 void * Array[∞]; // An infinite array 3 void enqueue(void * p) 4 while True do 5 T = FAA(&Tail, 1); // Repeat the loop if the entry is // already invalidated by dequeue() 6 if ( SWAP(&Array[T], p) = ⊥ ) 7 return; 8 void * dequeue() 9 while True do 10 H = FAA(&Head, 1); 11 p = SWAP(&Array[H], >); 12 if ( p , ⊥ ) return p; 13 if ( L… view at source ↗
Figure 4
Figure 4. Example: storing pointers. array entry, and inserts the index into aq. A consumer thread dequeues the index from aq, reads data from the array, and inserts the entry back into fq. Both queues maintain Head and Tail references ( [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 5
Figure 5. Naive circular queue (NCQ). Tail are both n (cycle 1). Full queues initialize all entries to cycle 0 along with allocated entry indices. Their Head is 0 (cycle 0) and Tail is n (cycle 1). Entries are always updated sequentially. To reduce contention due to false sharing, we remap queue entry positions by using a simple permutation function, Cache_Remap, that places two adjacent entries into di erent cache lines. The… view at source ↗
Figures from the paper (9 more)
Figure 6
Figure 6. Figure 6: Innite array queue. (We make it livelock-free by using a “threshold”.) [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 7
Figure 7. Figure 7: Threshold bound for livelock prevention. [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: Scalable circular queue (SCQ). arrives, it will fail. For this purpose, we clear the IsSafe bit, as in CRQ. The key idea is that the enqueuer will have to additionally make sure that all active dequeuers are behind when IsSafe is set to 0 (Line 16) before inserting a n…
Figure 9
Figure 9. Figure 9: Unbounded SCQ-based queue (LSCQ). 5.3 SCQ-based unbounded queue (LSCQ) We follow LCRQ’s main idea of maintaining a list of ring bu ers in our LSCQ design. LSCQ is potentially more memory e cient than LCRQ, as it is based on livelock-free SCQs which do not end up being …
Figure 10
Figure 10. Figure 10: SCQ for double-width CAS: checking for full queues. [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]
Figure 11
Figure 11. Figure 11: Empty queue test, throughput of the dequeue operation. [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]
Figure 12
Figure 12. Figure 12: Memory e ciency test, 4x18-core Intel Xeon E7-8880 (standard malloc). [PITH_FULL_IMAGE:figures/full_fig_p013_12.png]
Figure 13
Figure 13. Figure 13: Balanced load tests, 4x18-core Intel Xeon E7-8880. [PITH_FULL_IMAGE:figures/full_fig_p013_13.png]
Figure 14
Figure 14. Figure 14: Balanced load tests, 8x8-core POWER8. In Figures 13b and 14b, we present results for an experiment which selects operations randomly: 50% of enqueues and 50% of dequeues. For x86-64, WFQUEUE and SCQP are almost identical. SCQP marginally out￾performs SCQ when concurre…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [19]

    Morrison and Y

    A. Morrison and Y. Afek. Fast Concurrent Queues for x86 Processors. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP ’13, pages 103–112, New York, NY, USA, 2013. ACM

    work page 2013

  2. [1]

    ARM Architecture Reference Manual

    Arm Limited. ARM Architecture Reference Manual. http://developer.arm.com/, 2019

    work page 2019

  3. [2]

    J. Evans. A scalable concurrent malloc(3) implementation for FreeBSD. In Proceedings of the BSDCan Conference, Ottawa, Canada, 2006

    work page 2006

  4. [3]

    Fatourou and N

    P. Fatourou and N. D. Kallimanis. Revisiting the Combining Synchronization Technique. InProceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP ’12, pages 257–266, New York, NY, USA, 2012. ACM

    work page 2012

  5. [4]

    Feldman and D

    S. Feldman and D. Dechev. A Wait-free Multi-producer Multi-consumer Ring Buffer. ACM SIGAPP Applied Computing Review, 15(3):59–71, Oct. 2015

    work page 2015

  6. [5]

    Freudenthal and A

    E. Freudenthal and A. Gottlieb. Process Coordination with Fetch-and-increment. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems , ASPLOS IV, pages 260–268, 1991

    work page 1991

  7. [6]

    Hendler, N

    D. Hendler, N. Shavit, and L. Yerushalmi. A Scalable Lock-free Stack Algorithm. InProceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’04, pages 206–215, New York, NY, USA, 2004. ACM

    work page 2004

  8. [7]

    PowerPC Architecture Book, Version 2.02

    IBM. PowerPC Architecture Book, Version 2.02. Book I: PowerPC User Instruction Set Architecture. http://www.ibm.com/developerworks/, 2005

    work page 2005

Show all 24 references
  1. [8]

    Intel 64 and IA-32 Architectures Developer’s Manual

    Intel. Intel 64 and IA-32 Architectures Developer’s Manual. http://www.intel.com/, 2019

    2019

  2. [9]

    C. M. Kirsch, M. Lippautz, and H. Payer. Fast and Scalable, Lock-Free k-FIFO Queues. In Proceedings of the 12th International Conference on Parallel Computing Technologies - Volume 7979 , pages 208–223, Berlin, Heidelberg, 2013. Springer-Verlag

    2013

  3. [10]

    Krizhanovsky

    A. Krizhanovsky. Lock-free Multi-producer Multi-consumer Queue on Ring Buffer. Linux J., 2013(228), 2013

    2013

  4. [11]

    L. Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers , 28(9):690–691, Sept. 1979. 15

    1979

  5. [12]

    Lock-free Data Structure Library

    Liblfds. Lock-free Data Structure Library. http://www.liblfds.org

  6. [13]

    Ringbuffer disappointment

    Liblfds. Ringbuffer disappointment. http://www.liblfds.org/wordpress/index.php/2016/04/29/ ringbuffer-disappointment/

    2016

  7. [14]

    Memory Allocator Benchmarks

    Lockless Inc. Memory Allocator Benchmarks. https://locklessinc.com/benchmarks_allocator. shtml, 2019

    2019

  8. [15]

    M. M. Michael. Hazard pointers: safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems , 15(6):491–504, June 2004

    2004

  9. [16]

    M. M. Michael and M. L. Scott. Nonblocking Algorithms and Preemption-Safe Locking on Multipro- grammed Shared Memory Multiprocessors. Journal of Parallel and Distributed Computing , 51(1):1–26, May 1998

    1998

  10. [17]

    MIPS32/MIPS64 Rev

    MIPS. MIPS32/MIPS64 Rev. 6.06. http://www.mips.com/products/architectures/, 2019

    2019

  11. [18]

    M. Moir, D. Nussbaum, O. Shalev, and N. Shavit. Using Elimination to Implement Scalable and Lock-free FIFO Queues. In Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures , SPAA ’05, pages 253–262, 2005

    2005

  12. [20]

    SPARC Architecture 2011

    Oracle. SPARC Architecture 2011. http://www.oracle.com/, 2019

    2011

  13. [21]

    RISC-V Books

    RISC-V Foundation. RISC-V Books. http://riscv.org/risc-v-books/, 2019

    2019

  14. [22]

    Tsigas and Y

    P. Tsigas and Y. Zhang. A Simple, Fast and Scalable Non-blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, SPAA ’01, pages 134–143, 2001

    2001

  15. [23]

    D. Vyukov. Bounded MPMC queue. http://www.1024cores.net/home/lock-free-algorithms/ queues/bounded-mpmc-queue

  16. [24]

    Yang and J

    C. Yang and J. Mellor-Crummey. A Wait-free Queue As Fast As Fetch-and-add. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP ’16, pages 16:1– 16:13, New York, NY, USA, 2016. ACM. 16

    2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.