Pith. sign in

REVIEW 3 major objections 4 minor 65 references

Aggregating Funnels for Faster Fetch&Add and Queues

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

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

Pith's one-line read Aggregating Funnels batch fetch-and-add operations across many memory locations, cutting contention and speeding up state-of-the-art queues, while remaining strongly linearizable.

desk verdict A genuinely new combining mechanism for fetch-and-add with a mostly sound proof, but the abstract overclaims: correctness holds only under an unstated bound on argument size, and the experiments omit the overflow-handling path. read the letter →

arxiv 2411.14420 v2 pith:2UWTWNQJ submitted 2024-11-21 cs.DC

Younghun Roh , Yuanhao Wei , Eric Ruppert , Panagiota Fatourou , Siddhartha Jayanti , Julian Shun This is my paper · ORCID
classification cs.DC
keywords fetch-and-addsoftwarecombiningcontentionreductionstronglinearizabilityconcurrentqueuesLCRQaggregatingfunnelsshared-memoryalgorithms
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 presents Aggregating Funnels, a software implementation of fetch-and-add that spreads contention across many memory locations instead of concentrating every operation on one hot spot. Each Fetch&Add does one hardware fetch-and-add on an Aggregator's value field; threads that land together form a batch, and only the batch's delegate performs a fetch-and-add on the main variable. The implementation is proved strongly linearizable, so it can replace hardware fetch-and-add in any concurrent algorithm that uses the primitive. Experiments show up to 4x throughput over hardware fetch-and-add and Combining Funnels at high thread counts, and replacing fetch-and-add in the LCRQ queue improves throughput up to 2.5x.

What carries the argument

The load-bearing object is the Aggregator, an ancillary shared memory cell whose 64-bit value field only increases, paired with an immutable singly-linked list of Batch records. A Fetch&Add with argument $df$ does F&A($|df|$) on the Aggregator's value; the returning $aBefore$ locates the operation in a batch. The first operation in a batch, the one whose $aBefore$ equals the previous Batch's $after$, becomes delegate, reads $aAfter$, applies F&A(Main, $(aAfter-aBefore)\cdot \mathrm{sgn}(df)$), and appends a new Batch storing $aBefore$, $aAfter$, and $mainBefore$. Non-delegates walk the Batch list and return $mainBefore + (aBefore-batch.before)\cdot \mathrm{sgn}(df)$. This one-instruction registration closes the batch, selects the delegate, sums the operations, and gives every operation the data it needs to compute its result.

What would settle it

Run Algorithm 1 on hardware whose F&A wraps around modulo $2^{64}$, with $p$ threads issuing positive arguments whose sum on one Aggregator exceeds $2^{64}$ (for example, two arguments of $2^{63}$ each), and compare each operation's returned value against the sequential order of the batch's linearization at Main; any mismatch falsifies the linearizability claim.

Watch

Extended reading notes

Core claim

The central discovery is that a single hardware F&A per operation, aimed at one of several Aggregator value fields, is enough to batch operations and still return every caller the value hardware F&A would have returned. An operation's F&A on the Aggregator both registers it in a batch and tells it whether it is the first (delegate) operation of that batch; the delegate reads the Aggregator's accumulated value, applies the batch's total to Main with one F&A, and appends an immutable Batch record containing the before and after values and Main's prior value. Every other operation in the batch finds its Batch record and computes its return value from the difference between its F&A result and the batch's before field. Linearizing the whole batch at the delegate's F&A on Main preserves the order in which operations hit the Aggregator, and the proof shows this order is consistent with each operation's invocation and response, hence strongly linearizable.

Load-bearing premise

The proof assumes every Fetch&Add argument has absolute value less than $2^{63}/p$, where $p$ is the thread count, so no Aggregator's 64-bit value can overflow; if a thread supplies a larger argument, the batch-ordering invariant and the linearizability guarantee no longer hold.

Editorial extensions

If this is right

  • Because Algorithm 1 is strongly linearizable, applications that require the stronger property for randomized algorithms can replace a hardware F&A with this Fetch&Add object and preserve correctness; ordinary linearizable applications can do so as well.
  • At thread counts above about 30, the aggregate throughput of Fetch&Add operations is up to 4 times higher than hardware F&A and Combining Funnels, and the improvement grows with thread count on all machines tested.
  • Replacing the fetch-and-add objects in LCRQ raises queue throughput by up to 2.5x, showing the contention reduction remains effective inside a real data structure rather than only in microbenchmarks.
  • A Fetch&AddDirect operation gives selected threads a low-latency path straight to Main; in experiments one or two high-priority threads can get up to 40x the throughput of low-priority threads without reducing total throughput.
  • Applying the construction recursively by replacing Main with another instance reduces the worst-case contention on any memory location to $O(p^{1/(k+1)})$ after $k$ replacements, at the cost of $\Theta(\log p)$ accesses per operation when $k=\log_2 p$.

Reading between the lines

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

  • A testable extension is to make Aggregator choice NUMA-aware: since Algorithm 2 partitions threads into $\sqrt{p}$ groups, a socket-local grouping could reduce cross-socket traffic on machines with multiple processors, at the possible cost of uneven batch sizes.
  • The overflow-bounded proof suggests that an implementation with 128-bit or wrap-safe Aggregator values, or a retry scheme for oversized arguments, would extend the linearizability guarantee to unbounded workloads; the paper only sketches the threshold parameter and the practical implementation omits the overflow path.
  • Because every Read in the base algorithm touches Main, a read-aggregating counterpart could reduce Main contention in read-heavy workloads; the paper's experiments show Reads dominate contention at 50% and 10% Fetch&Add mixes but no such variant is evaluated.
  • The Fetch&AddDirect path could be scheduled dynamically rather than reserved for fixed high-priority threads; for example, a low-priority thread that finds its Aggregator's batch list long might switch to Main and affect the latency-throughput tradeoff, an option the paper does not explore.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper presents Aggregating Funnels, a software Fetch&Add algorithm that reduces contention by spreading operations over multiple aggregator objects. Each aggregator batches concurrent operations using a single hardware F&A per operation; a delegate applies the batch sum to a main variable, and non-delegates compute their results from immutable batch metadata. The authors prove strong linearizability of the algorithm, describe a recursive variant to further reduce contention, and present experiments on a 176-thread machine showing up to 4x throughput over hardware F&A and Combining Funnels in microbenchmarks, and up to 2.5x improvement in the LCRQ concurrent queue.

Significance. If the correctness claims hold, this is a significant practical contribution: a simple Fetch&Add combining scheme using only Load, Store, and F&A instructions that scales better than hardware F&A, with a detailed proof of strong linearizability and a publicly available artifact. The experiments are thorough, covering multiple workloads, machines, and an application-level queue benchmark. The proof structure (Invariant 3.1, Lemmas 3.2 and 3.4, Theorem 3.5) is clear and matches the pseudocode. However, the central theorem is stated without an input restriction that the proof actually requires, and the algorithm as presented has an unbounded-memory behavior that contradicts the paper's space claim; these issues need to be addressed before the results can be accepted as stated.

major comments (3)
  1. [Theorem 3.5 and Section 3.1.1] Theorem 3.5 states that Algorithm 1 is a strongly linearizable implementation of a Fetch&Add object, without any restriction on arguments. However, the proof of Invariant 3.1 explicitly relies on 'A.value never overflows by the argument in Section 3.1.1', and Section 3.1.1 guarantees this only when every argument to Fetch&Add has absolute value strictly less than 2^63/p (or more generally 2^64 - p·B). This bound is not stated in the theorem, the abstract, or the contributions. The cyan overflow-handling code cannot prevent an overflow if several large arguments arrive before a delegate reads A.value on line 27; a wrap can occur before any retirement, breaking the monotonicity needed by Invariant 3.1 and the batch-identification logic of lines 35-37. The theorem and the paper's claims of a general Fetch&Add object must either state the required input bound explicitly or the overflow-handling mechanism must be redesigned.
  2. [Section 3.1.2] The space complexity claim is incorrect. The text says 'a Batch is retired as soon as it is not pointed to by an Aggregator' and concludes that at most Θ(m) Aggregator and Batch objects have not yet been retired. In Algorithm 1, each new Batch's previous pointer points to the prior a.last, and no batch is ever unlinked while its Aggregator is active. Thus every historical batch remains reachable from a.last, and no batch is retired. Because a delayed operation can traverse arbitrarily far back along the previous chain, no old batch can be safely reclaimed. The batch list grows without bound with the total number of operations, so memory usage is not Θ(m) but Θ(total operations) in the worst case. The paper's own admission that it cannot prove a worst-case memory bound conflicts with the subsequent Θ(m) claim.
  3. [Section 4.1] The experiments are run with the simpler version of Algorithm 1 without the cyan overflow-handling code. Therefore the reported speedups (e.g., up to 4x for Fetch&Add, 2.5x for LCRQ) are measured for a restricted variant whose correctness is proven only under an input assumption, and the overhead of the full algorithm is unmeasured. The statement 'We believe the overhead added by the overflow handling code should be insignificant' is not a substitute for measurement. At minimum, the paper should report whether the full algorithm was benchmarked and, if not, explicitly quantify the common-case overhead of the additional checks in lines 23-24 and the retirement path in lines 29-32.
minor comments (4)
  1. [Section 4.5] There is a typo: 'throguhput' should be 'throughput'.
  2. [Artifact appendix A.2] The artifact checklist says 'Graphs from Section 3 as png files' but the experimental graphs are in Section 4; this should be corrected.
  3. [Section 3.2] The recursive construction's linearizability is asserted by replacing an atomic object with a linearizable implementation. This is plausible, but the proof of Lemmas 3.2 and 3.4 assumes that the F&A on Main on line 28 is an atomic step; when Main is itself an Aggregating Funnels instance, the linearization point of the outer batch must be shifted to the inner object's linearization point. A short argument for this composition would make the section self-contained.
  4. [Section 3.1.2] The first sentence says 'Our implementation in Section 4 uses epoch-based reclamation' but Section 4 is the experimental evaluation; this should refer to the experimental implementation presented there, not the algorithm section.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the correctness proof is self-contained and the experimental claims are measured, not derived from a fitted model; the overflow input restriction is a robustness caveat, not a circular step.

full rationale

The derivation chain is self-contained. Algorithm 1 is defined by explicit pseudocode, and Theorem 3.5 is proved from Invariant 3.1, Lemma 3.2, Invariant 3.3, and Lemma 3.4 using only properties of the code, such as monotonic aggregator values and the before/after fields of Batch objects. No equation defining a key quantity is reused as the result. The overflow restriction in Section 3.1.1, 'provided every argument to Fetch&Add is strictly less than 2^63/p in absolute value,' is an explicit input condition used to prevent Aggregator overflow; Theorem 3.5 omits that condition, which is a correctness-robustness gap rather than a circular reduction of the conclusion to the premise. Section 4 performance claims are direct measurements of throughput, batch size, fairness, and queue speedup; the choice of m = 6 is an empirically tuned parameter, and the paper reports results for several m values, so there is no fitted parameter relabeled as a prediction. The self-citations that appear (References [14], [31], [33], and [54]) are definitional, lower-bound, or future-work references and are not load-bearing for the central linearizability or performance claims. The Combining Funnels baseline is prior external work, not an argument imported from the present authors. No uniqueness theorem or ansatz is smuggled in via citation to force the construction. Therefore no circular step is present.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The algorithm assumes atomic Read/Write/F&A, appropriately fenced weak memory, bounded arguments for overflow safety, and epoch-based reclamation. The only performance parameter is m, the number of aggregators per sign, which is tuned in experiments but does not affect correctness. No new physical entities are introduced; Aggregator and Batch are ordinary data structures.

free parameters (2)
  • m (number of Aggregators per sign) = 6 (default; Algorithm 2 uses ceil(sqrt(p)))
    Performance knob: more aggregators reduce contention at each aggregator but increase contention on Main. Chosen as m=6 after experiments; correctness holds for any m.
  • Threshold for Aggregator retirement = 2^63
    Set so that with p threads and arguments bounded by B < 2^63/p, A.value never reaches 2^64. Not fitted to data; derived from overflow bound.
assumptions (4)
  • domain assumption Hardware F&A is atomic and linearizable.
    Algorithm 1 uses F&A on shared variables as the primitive; Section 3 states this.
  • domain assumption Reads and writes are sequentially consistent or made so with fences.
    Proofs in Section 3.3 assume interleaving semantics; Section 4.1 says fences are added for weak memory models.
  • domain assumption Every Fetch&Add argument satisfies |df| < 2^63/p to prevent Aggregator overflow.
    Section 3.1.1 requires this bound for the overflow-safe version; without it, A.value can wrap and invalidate Invariant 3.1.
  • domain assumption Epoch-based reclamation keeps Batch and Aggregator objects alive while referenced.
    Section 3.1.2 relies on epoch-based reclamation for memory safety; the correctness proof does not model reclamation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Aggregating Funnels for Faster Fetch&Add and Queues." pith.science (2026). https://pith.science/paper/2UWTWNQJ

@misc{pith2026241114420,
  author       = {Pith},
  title        = {Pith review of: Aggregating Funnels for Faster Fetch&Add and Queues},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2UWTWNQJ}},
  note         = {Machine review of arXiv:2411.14420}
}
read the original abstract

Many concurrent algorithms require processes to perform fetch-and-add operations on a single memory location, which can be a hot spot of contention. We present a novel algorithm called Aggregating Funnels that reduces this contention by spreading the fetch-and-add operations across multiple memory locations. It aggregates fetch-and-add operations into batches so that the batch can be performed by a single hardware fetch-and-add instruction on one location and all operations in the batch can efficiently compute their results by performing a fetch-and-add instruction on a different location. We show experimentally that this approach achieves higher throughput than previous combining techniques, such as Combining Funnels, and is substantially more scalable than applying hardware fetch-and-add instructions on a single memory location. We show that replacing the fetch-and-add instructions in the fastest state-of-the-art concurrent queue by our Aggregating Funnels eliminates a bottleneck and greatly improves the queue's overall throughput.

Figures

Figures reproduced from arXiv: 2411.14420 by the authors.

Figure 1
Figure 1. Example execution with five Fetch&Add opera￾tions and two Aggregator objects 𝐴1 and 𝐴2. 23 for 𝑜𝑝𝑑𝑒𝑙 to add its Batch to 𝐴’s batch list: only then will 𝑜𝑝′ 𝑑𝑒𝑙 evaluate the condition of the wait statement on line 23 to be false and proceed to execute lines 26–33 itself. A Fetch&Add operation op on 𝑂 computes its result as follows. If op is the first operation within its batch on Aggregator 𝐴 (i.e., it is the delegat… view at source ↗
Figure 2
Figure 2. Example of recursive construction with 𝑝 = 8. reduces contention on any location to 𝑂(𝑝 1/2 𝑘 ). Taking 𝑘 = log log 𝑝 yields 𝑂(1) contention using 𝑂(𝑝) Aggregators. There is a tradeoff: reducing contention on individual locations requires a Fetch&Add to access more locations (or wait for others to do so). Moreover, when a Fetch&Add operation must access more locations, it spends a smaller fraction of its time at eac… view at source ↗
Figure 3
Figure 3. Fetch&Add performance with different numbers of Aggregators. 4.1 Experimental Setup We used Google Cloud Platform’s c3-standard-176 instance, which has four 4th Gen Intel Xeon Platinum 8481C proces￾sors with a total of 176 hyper-threads with 2-way hyper￾threading, and 704GB of main memory. We also briefly dis￾cuss results on an AMD machine and older Intel machines at the end of Section 4.3. Our Fetch&Add and queue b… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Comparing throughput and fairness of Aggregating Funnels, Combining Funnels, and hardware F&A. HardwareF&A AggFunnel-(6,0) AggFunnel-(6,1) AggFunnel-(6,2) AggFunnel-(2,0) AggFunnel-(2,1) AggFunnel-(2,2) 0 50 100 150 Number of threads 0 20 40 60 Throughput (Mops/s) (a) …
Figure 5
Figure 5. Figure 5: Fetch&Add performance with high-priority threads. 90% Fetch&Add, 32 cycles of additional work. Figure 5a shows throughput for different parameters. With 𝑚 = 6, the total throughput was not significantly affected by having high-priority threads. However, with 𝑚 = 2, the…
Figure 6
Figure 6. Figure 6: Queue performance using different fetch-and-add implementations in LCRQ. 4.5 Queue Benchmark Since our Fetch&Add algorithm supports all hardware prim￾itives, we can easily replace a hardware F&Aobject in various applications to mitigate the contention bottleneck. As me…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 40 canonical work pages

  1. [1]

    Yehuda Afek, Dalia Dauber, and Dan Touitou. 1995. Wait-free made fast. In Proc. 27th ACM Symposium on Theory of Computing . 538–547. https://doi.org/10.1145/225058.225271

    work page arXiv 1995

  2. [2]

    Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Morteza Zadimoghaddam. 2011. Optimal-time adaptive strong renam- ing, with applications to counting. In Proc. 30th ACM Symposium on Principles of Distributed Computing . 239–248. https://doi.org/10.1145/ 1993806.1993850

    arXiv 2011

  3. [3]

    Anderson

    T.E. Anderson. 1990. The performance of spin lock alternatives for shared-money multiprocessors. IEEE Transactions on Parallel and Distributed Systems 1, 1 (1990), 6–16. https://doi.org/10.1109/71.80120

    doi:10.1109/71.80120 1990

  4. [4]

    James Aspnes, Maurice Herlihy, and Nir Shavit. 1994. Counting net- works. J. ACM 41, 5 (Sept. 1994), 1020–1048. https://doi.org/10.1145/ 185675.185815

    work page arXiv 1994

  5. [5]

    Benyamin Bashari, Ali Jamadi, and Philipp Woelfel. 2023. Efficient Bounded Timestamping from Standard Synchronization Primitives. In Proc. ACM Symposium on Principles of Distributed Computing . 113–123. https://doi.org/10.1145/3583668.3594601

    work page arXiv 2023

  6. [6]

    Blelloch

    Naama Ben-David, Ziv Scully, and Guy E. Blelloch. 2019. Unfair Sched- uling Patterns in NUMA Architectures. In Proc. 28th International Con- ference on Parallel Architectures and Compilation Techniques . 205–218. https://doi.org/10.1109/PACT.2019.00024

    arXiv 2019

  7. [7]

    David Dice, Ori Shalev, and Nir Shavit. 2006. Transactional Locking II. In Proc. 20th International Symposium on Distributed Computing (LNCS, Vol. 4167). Springer, 194–208. https://doi.org/10.1007/11864219_14

    doi:10.1007/11864219_14 2006

  8. [8]

    Faith Ellen and Philipp Woelfel. 2013. An Optimal Implementation of Fetch-and-Increment. In Proc. 27th International Symposium on Dis- tributed Computing (LNCS, Vol. 8205) . 284–298. https://doi.org/10. 1007/978-3-642-41527-2_20

    work page 2013

Show all 65 references
  1. [9]

    Carla Schlatter Ellis and Thomas J. Olson. 1988. Algorithms for parallel memory allocation. International Journal of Parallel Programming 17, 4 (1988), 303–345. https://doi.org/10.1007/BF01407909

    1988 doi

  2. [10]

    Panagiota Fatourou, Nikos Giachoudis, and George Mallis. 2024. Highly-Efficient Persistent FIFO Queues. In Proc. 31st International Colloquium on Structural Information and Communication Complexity (LNCS, Vol. 14662). 238–261. https://doi.org/10.1007/978-3-031-60603- 8_14

    2024 doi

  3. [11]

    Panagiota Fatourou and Maurice Herlihy. 2004. Read-modify-write networks. Distributed Computing 17, 1 (2004), 33–46. https://doi.org/ 10.1007/S00446-003-0097-5

    2004 doi

  4. [12]

    Kallimanis

    Panagiota Fatourou and Nikolaos D. Kallimanis. 2012. Revisiting the combining synchronization technique. In Proc. 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 257–266. https://doi.org/10.1145/2145816.2145849

    2012

  5. [13]

    Kallimanis

    Panagiota Fatourou and Nikolaos D. Kallimanis. 2014. Highly-Efficient Wait-Free Synchronization. Theory of Computing Systems 55, 3 (2014), 475–520. https://doi.org/10.1007/S00224-013-9491-Y

    2014 doi

  6. [14]

    Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. 2019. Per- sistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries. In Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures. 275–286. https://doi.org/10.1145/3323165.3323197

    2019

  7. [15]

    Michael J. Fischer. 1983. The consensus problem in unreliable dis- tributed systems (a brief survey). InFoundations of Computation Theory, Marek Karpinski (Ed.). Springer, Berlin, 127–140

    1983

  8. [16]

    Fischer, Nancy A

    Michael J. Fischer, Nancy A. Lynch, James E. Burns, and Allan Borodin

  9. [17]

    M. J. Fischer, S. Moran, S. Rudich, and G. Taubenfeld. 1990. The wakeup problem. In Proc. 22nd ACM Symposium on Theory of Computing . 106–

    1990

  10. [18]

    2003.Practical lock-freedom

    Keir Fraser. 2003.Practical lock-freedom. Ph. D. Dissertation. University of Cambridge. Technical report based on thesis is available from https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf

    2003

  11. [19]

    Eric Freudenthal and Allan Gottlieb. 1991. Process coordination with fetch-and-increment. In Proc. 4th International Conference on Archi- tectural Support for Programming Languages and Operating Systems . 260–268. https://doi.org/10.1145/106972.106998

    1991

  12. [20]

    Golab, Lisa Higham, and Philipp Woelfel

    Wojciech M. Golab, Lisa Higham, and Philipp Woelfel. 2011. Lin- earizable implementations do not suffice for randomized distributed computation. In Proc. 43rd ACM Symposium on Theory of Computing . 373–382. https://doi.org/10.1145/1993636.1993687

    2011

  13. [21]

    Goodman, Mary K

    James R. Goodman, Mary K. Vernon, and Philip J. Woest. 1989. Effi- cient synchronization primitives for large-scale cache-coherent mul- tiprocessors. In Proc. 3rd International Conference on Architectural Support for Programming Languages and Operating Systems . 64–75. https:/...

    1989

  14. [22]

    Allan Gottlieb and Clyde P. Kruskal. 1981. Coordinating parallel processors: a partial unification. SIGARCH Computure Architecture News 9, 6 (Oct. 1981), 16–24. https://doi.org/10.1145/859515.859517

    1981

  15. [23]

    Lubachevsky, and Larry Rudolph

    Allan Gottlieb, Boris D. Lubachevsky, and Larry Rudolph. 1983. Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors. ACM Transactions on Programming Languages and Systems (TOPLAS) 5, 2 (April 1983), 164–189. https: //doi.or...

    1983

  16. [24]

    Maurice Herlihy, Beng-Hong Lim, and Nir Shavit. 1995. Scalable concurrent counting. Theory of Computing Systems (TOCS) 13, 4 (Nov. 1995), 343–364. https://doi.org/10.1145/210223.210225

    1995

  17. [25]

    Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear

  18. [26]

    Maurice Herlihy, Nir Shavit, and Orli Waarts. 1996. Linearizable Counting Networks. Distributed Computing 9, 4 (1996), 193–203. https://doi.org/10.1007/S004460050019

    1996 doi

  19. [27]

    Herlihy and Jeannette M

    Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (July 1990), 463–

    1990

  20. [28]

    Intel. 2020. Intel 64 and IA-32 Architectures Software Developer Man- uals. https://software.intel.com/content/www/us/en/develop/articles/ intel-sdm.html

    2020

  21. [29]

    Prasad Jayanti. 1998. A time complexity lower bound for randomized implementations of some shared objects. InProc. 17th ACM Symposium on Principles of Distributed Computing . 201–210. https://doi.org/10. 1145/277697.277735

    1998

  22. [30]

    Prasad Jayanti. 2002. 𝑓 -arrays: implementation and applications. In Proc. 21st ACM Symposium on Principles of Distributed Computing . 270–279. https://doi.org/10.1145/571825.571875

    2002

  23. [31]

    Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti. 2024. Mem- Snap: A Fast Adaptive Snapshot Algorithm for RMWable Shared- Memory. In Proc. 43rd ACM Symposium on Principles of Distributed Computing. 25–35. https://doi.org/10.1145/3662158.3662820

    2024

  24. [32]

    Tarjan, and Enric Boix-Adserà

    Siddhartha Jayanti, Robert E. Tarjan, and Enric Boix-Adserà. 2019. Randomized Concurrent Set Union and Generalized Wake-Up. In Proc. ACM Symposium on Principles of Distributed Computing . 187–

    2019

  25. [33]

    Siddhartha Visveswara Jayanti. 2022. Generalized Wake-Up: Amor- tized Shared Memory Lower Bounds for Linearizable Data Structures [in Telugu]. (2022). arXiv:2207.07561 [cs.DS] Manuscript available from https://arxiv.org/abs/2207.07561

    2022 arXiv

  26. [34]

    Korach, S

    E. Korach, S. Moran, and S. Zaks. 1984. Tight lower and upper bounds for some distributed algorithms for a complete network of processors. In Proc. 3rd ACM Symposium on Principles of Distributed Computing . 199–207. https://doi.org/10.1145/800222.806747

    1984

  27. [35]

    Marios Mavronicolas. 2000. Annotated Bibliography on Counting Networks. Bull. EATCS 72 (2000), 123–132. PPoPP ’25, March 1–5, 2025, Las Vegas, NV, USA Younghun Roh, Yuanhao Wei, Eric Ruppert, Panagiota Fatourou, Siddhartha Jayanti, and Julian Shun

    2000

  28. [36]

    Mellor-Crummey and Michael L

    John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. Theory of Computing Systems (TOCS) 9, 1 (Feb. 1991), 21–65. https://doi.org/ 10.1145/103727.103729

    1991

  29. [37]

    Michael and Michael L

    Maged M. Michael and Michael L. Scott. 1995. Correction of a Memory Management Method for Lock-Free Data Structures . Technical Report

    1995

  30. [38]

    Anderson

    Mark Moir and James H. Anderson. 1995. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming 25, 1 (1995), 1–39. https://doi.org/10.1016/0167-6423(95)00009-H

    1995 doi

  31. [39]

    Adam Morrison and Yehuda Afek. 2013. Fast concurrent queues for x86 processors. In Proc. ACM Symposium on Principles and Practice of Parallel Programming . 103–112. https://doi.org/10.1145/2442516. 2442527

    2013 doi

  32. [40]

    Ruslan Nikolaev. 2019. A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue. In Proc. 33rd International Symposium on Dis- tributed Computing (LIPIcs, Vol. 146) . 28:1–28:16. https://doi.org/10. 4230/LIPIcs.DISC.2019.28

    2019

  33. [41]

    Ruslan Nikolaev and Binoy Ravindran. 2022. wCQ: A Fast Wait-Free Queue with Bounded Memory Usage. In Proc. 34th ACM Symposium on Parallelism in Algorithms and Architectures . 307–319. https://doi. org/10.1145/3490148.3538572

    2022

  34. [42]

    Yaqiong Peng and Zhiyu Hao. 2018. FA-Stack: A Fast Array-Based Stack with Wait-Free Progress Guarantee.IEEE Transactions on Parallel and Distributed Systems 29, 4 (2018), 843–857. https://doi.org/10.1109/ TPDS.2017.2770121

    2018

  35. [43]

    Peterson

    Gary L. Peterson. 1982. An 𝑂(𝑛 log 𝑛) Unidirectional Algorithm for the Circular Extrema Problem. ACM Transactions on Programming Languages and Systems (TOPLAS) 4, 4 (Oct. 1982), 758–762. https: //doi.org/10.1145/69622.357194

    1982

  36. [44]

    Reed and Rajendra K

    David P. Reed and Rajendra K. Kanodia. 1979. Synchronization with eventcounts and sequencers. Commun. ACM 22, 2 (Feb. 1979), 115–123. https://doi.org/10.1145/359060.359076

    1979

  37. [45]

    Raed Romanov and Nikita Koval. 2023. The State-of-the-Art LCRQ Concurrent Queue Algorithm Does NOT Require CAS2. In Proc. 28th ACM SIGPLAN Symposium on Principles and Practice of Parallel Pro- gramming. 14–26. https://doi.org/10.1145/3572848.3577485 Software artifact available...

    2023

  38. [46]

    Nir Shavit and Dan Touitou. 1997. Elimination Trees and the Construc- tion of Pools and Stacks. Theory of Computing Systems 30, 6 (1997), 645–670. https://doi.org/10.1007/S002240000072

    1997 doi

  39. [47]

    Nir Shavit and Asaph Zemach. 1996. Diffracting trees. Theory of Computing Systems (TOCS) 14, 4 (Nov. 1996), 385—-428. https://doi. org/10.1145/235543.235546

    1996

  40. [48]

    Nir Shavit and Asaph Zemach. 2000. Combining Funnels: A Dynamic Approach to Software Combining.J. of Parallel and Distributed Comput- ing 60, 11 (2000), 1355–1387. https://doi.org/10.1006/JPDC.2000.1621

    2000

  41. [49]

    Harold S. Stone. 1982. Parallel Memory Allocation using the FETCH- AND-ADD Instruction. Technical Report RC 9674. IBM Research. 14 pages

    1982

  42. [50]

    Harold S. Stone. 1984. Database Applications of the FETCH-AND- ADD Instruction. IEEE Trans. Comput. C-33, 7 (1984), 604–612. https: //doi.org/10.1109/TC.1984.5009333

    1984

  43. [51]

    Håkan Sundell. 2005. Wait-free reference counting and memory man- agement. In Proc. 19th IEEE International Parallel and Distributed Pro- cessing Symposium. https://doi.org/10.1109/IPDPS.2005.451

    2005 doi

  44. [52]

    Peiyi Tang and Pen-Chung Yew. 1990. Software combining algorithms for distributing hot-spot addressing. J. Parallel and Distrib. Comput. 10, 2 (1990), 130–139. https://doi.org/10.1016/0743-7315(90)90022-H

    1990 doi

  45. [53]

    John D. Valois. 1995. Lock-free linked lists using compare-and-swap. In Proc. 14th ACM Symposium on Principles of Distributed Computing . 214–222. https://doi.org/10.1145/224964.224988

    1995

  46. [54]

    Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun

    Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun. 2021. Constant-time snapshots with applications to concurrent data structures. InProc. 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming . 31–46. https:/...

    2021

  47. [55]

    James M. Wilson. 1988. Operating System Data Structures for Shared- Memory MIMD Machines with Fetch-and-Add. Ph. D. Dissertation. New York University. Available from https://cs.nyu.edu/~gottlieb/family- tree

    1988

  48. [56]

    Chaoran Yang and John Mellor-Crummey. 2016. A wait-free queue as fast as fetch-and-add. In Proc. 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming . Article 16, 13 pages. https://doi.org/10.1145/2851141.2851168

    2016

  49. [57]

    Pen-Chung Yew, Nian-Feng Tzeng, and Lawrie. 1987. Distributing Hot- Spot Addressing in Large-Scale Multiprocessors. IEEE Trans. Comput. C-36, 4 (1987), 388–395. https://doi.org/10.1109/TC.1987.1676921 Aggregating Funnels for Faster Fetch&Add and Queues PPoPP ’25, March 1–5, 20...

    1987

  50. [64]

    Build the docker image (install docker if you haven’t) docker build –network=host –platform linux/amd64 -t aggfunnel

  51. [65]

    This command also complies all the necessary binaries

    Launch the docker container as an interactive shell. This command also complies all the necessary binaries. Remaining commands should be run inside the docker container.docker run -v .:/home/ubuntu/project -it –privileged –network=host aggfunnel Note: This command mounts the c...

  52. [116]

    https://doi.org/10.1145/100216.100228

  53. [196]

    https://doi.org/10.1145/3293611.3331593

  54. [492]

    https://doi.org/10.1145/78969.78972

  55. [599]

    Computer Science Department, University of Rochester

  56. [1979]

    Resource allocation with immunity to limited process failure. In Proc. 20th Symposium on Foundations of Computer Science . 234–254. https://doi.org/10.1109/SFCS.1979.37

    1979 doi

  57. [2021]

    Morgan Kauf- mann

    The Art of Multiprocessor Programming (2nd ed.). Morgan Kauf- mann

Pith tools

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