pith. sign in

arxiv: 2606.28889 · v1 · pith:IT7YBQCCnew · submitted 2026-06-27 · 💻 cs.DC · cs.DS

Concurrent Splay-Based Tree

Vitaly Aksenov , Rene van Bevern , Artem Shilkin This is my paper

Pith reviewed 2026-06-30 08:39 UTC · model grok-4.3

classification 💻 cs.DC cs.DS
keywords concurrent binary search treessplay treesskewed workloadsstatic optimalityrotation designaccess countersdistribution-adaptive indices
0
0 comments X

The pith

Concurrent binary search trees adapt to skewed access patterns using limited rotations controlled by two depth thresholds derived from access counts.

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

The paper develops a rotation scheme for concurrent ordered indices that responds to non-uniform access rates without the full cost of moving every accessed node to the root. Rotations occur only when a node exceeds an upper depth threshold and halt before a lower threshold, both computed from the node's access frequency via static-optimality analysis. This keeps the adaptation advantage of splay trees on highly skewed distributions while limiting contention at the root. Variants track accesses with either a full 64-bit counter or a compact 6-bit approximation. The design is proved statically optimal for the sequential read-only case and tested by adding the rotations to an existing concurrent tree implementation, where it raises throughput on several skewed workloads.

Core claim

A splay-like design rotates a node only when its depth substantially exceeds an upper threshold computed from its access count and stops rotations before reaching a lower threshold; the thresholds come from the static-optimality complexity bound. Two counter implementations are given, static optimality is proved for the sequential read-only version, and the method is shown to increase throughput on skewed workloads when layered on a concurrent AVL tree.

What carries the argument

Two depth thresholds derived from static-optimality complexity of access counts, which decide when rotations begin and where they stop to trade adaptation against root contention.

If this is right

  • The rotation rule preserves the main practical benefit of splaying on extremely skewed distributions.
  • Both exact and approximate counters can be used without changing the core rotation logic.
  • The same thresholds and proof apply when the structure is used only for reads in the sequential case.
  • Throughput gains appear on multiple skewed workloads when the rotations are added to an existing concurrent tree.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The threshold approach might be applied to other concurrent search structures that already support rotations.
  • Workload-specific threshold values could be derived if access counts are monitored over longer intervals.
  • The method could be tested on update-heavy workloads to check whether the contention reduction still holds when writes are frequent.

Load-bearing premise

The static-optimality thresholds will trigger rotations that cut root contention without adding synchronization overhead or violating correctness once the tree becomes concurrent.

What would settle it

A run of the modified concurrent tree on a Zipfian workload that produces no measurable throughput gain over the unmodified baseline or that returns incorrect search results.

read the original abstract

Most work on efficient concurrent ordered indices, such as concurrent binary search trees, B-trees, skip lists, etc., has focused on data structures that provide good \emph{worst-case} guarantees. In real workloads, objects are often accessed at different rates, since access distributions may be non-uniform. Many efficient distribution-adaptive data structures exist in the sequential case; however, they are often complicated to make efficient in the concurrent case. The most prominent distribution-adaptive data structure is Splay Tree. Its most important advantage is that it does not store any balancing information and provides a reasonable performance improvement on extremely skewed workloads, such as Zipfian workloads. This paper proposes a splay-like rotation design for concurrent binary search trees. Instead of moving an accessed node to the root, rotations use two depth thresholds that are based on the static-optimality complexity computed from the number of accesses to the node: a node is rotated only when it is substantially deeper than the upper threshold, and rotations of the node stop before reaching the lower threshold. This design aims to preserve the main practical benefit of splaying on skewed workloads while reducing contention near the root. We present two variants of the rotation design: one using an exact 64-bit access counter per node and one using a 6-bit approximate counter. We prove static optimality for the corresponding sequential read-only tree and evaluate both rotation designs by implementing them on top of the concurrent AVL tree of Bronson et al. Our experiments show that the approach can improve throughput on several skewed workloads.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper proposes a splay-like rotation design for concurrent binary search trees that performs partial rotations using two depth thresholds derived from static-optimality complexity, rather than full splaying to the root. Two variants are described (exact 64-bit and approximate 6-bit per-node access counters), implemented atop Bronson's concurrent AVL tree. Static optimality is proven for the corresponding sequential read-only tree, and experiments are reported to show throughput gains on several skewed workloads.

Significance. If the concurrent correctness, linearizability, and contention-reduction claims hold with the given thresholds, the work would offer a practical middle ground between worst-case concurrent trees and distribution-adaptive sequential structures, potentially useful for Zipfian workloads in ordered indices.

major comments (2)
  1. [Abstract] Abstract: the design claims to reduce contention near the root in the concurrent setting by using the same two depth thresholds derived from the sequential static-optimality analysis, yet no argument, invariant, or proof sketch is supplied showing that these thresholds preserve linearizability or avoid new synchronization costs when rotations are performed concurrently on Bronson's AVL tree; this is load-bearing for the central claim that the approach improves throughput without introducing correctness issues.
  2. [Design description (implied by abstract)] The manuscript states that static optimality holds only for the sequential read-only tree; the concurrent rotation protocol (including atomic updates to the 64-bit or 6-bit counters during rotations) therefore requires an explicit argument that the sequential thresholds do not invalidate the underlying tree's synchronization invariants or create new contention hotspots.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. The two major comments both identify the absence of an explicit argument for concurrent linearizability and synchronization invariants; we agree this is a gap and will address it directly in revision.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the design claims to reduce contention near the root in the concurrent setting by using the same two depth thresholds derived from the sequential static-optimality analysis, yet no argument, invariant, or proof sketch is supplied showing that these thresholds preserve linearizability or avoid new synchronization costs when rotations are performed concurrently on Bronson's AVL tree; this is load-bearing for the central claim that the approach improves throughput without introducing correctness issues.

    Authors: We agree that the manuscript supplies no explicit argument, invariant, or proof sketch for linearizability under concurrent rotations. The implementation performs rotations using the same atomic CAS primitives as Bronson's tree and updates counters atomically, but this reliance is only implicit. In the revised version we will add a dedicated subsection providing a sketch that the threshold conditions preserve the base tree's linearizability invariants because (i) every rotation is still a local, atomic transformation identical in structure to the original protocol and (ii) early termination before the root reduces rather than increases root contention. revision: yes

  2. Referee: [Design description (implied by abstract)] The manuscript states that static optimality holds only for the sequential read-only tree; the concurrent rotation protocol (including atomic updates to the 64-bit or 6-bit counters during rotations) therefore requires an explicit argument that the sequential thresholds do not invalidate the underlying tree's synchronization invariants or create new contention hotspots.

    Authors: We concur that an explicit argument is required once the manuscript acknowledges that static optimality is proven only for the sequential read-only case. The thresholds are intended to stop rotations short of the root precisely to avoid contention hotspots, and counter updates occur inside the same atomic sections used by Bronson's tree. In revision we will insert a short argument showing that the chosen depth thresholds do not create new synchronization points or invalidate the existing linearizability proof of the base structure. revision: yes

Circularity Check

0 steps flagged

No circularity; sequential proof and concurrent experiments are independent

full rationale

The paper defines depth thresholds from static-optimality complexity, proves static optimality only for the corresponding sequential read-only tree, and separately implements the rotation design on Bronson's concurrent AVL tree before reporting experimental throughput on skewed workloads. No parameter is fitted to a data subset and then renamed as a prediction of a related quantity; no self-citation chain justifies a uniqueness claim; no ansatz is smuggled via prior work; and the derivation does not reduce by construction to its inputs. The central result therefore rests on an external proof plus empirical measurement rather than tautological re-use of the same quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.1-grok · 5808 in / 1068 out tokens · 27237 ms · 2026-06-30T08:39:12.142888+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

234 extracted references · 79 canonical work pages · 3 internal anchors

  1. [1]

    International Journal of Foundations of Computer Science , volume=

    Efficient rebalancing of B-trees with relaxed balance , author=. International Journal of Foundations of Computer Science , volume=. 1996 , publisher=

    1996

  2. [2]

    Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures,

    Dan Alistarh and Trevor Brown and Justin Kopinsky and Jerry Zheng Li and Giorgi Nadiradze , title =. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures,. 2018 , crossref =. doi:10.1145/3210377.3210411 , timestamp =

    work page doi:10.1145/3210377.3210411 2018

  3. [3]

    and Tomari, Hisanobu , title =

    Nakaike, Takuya and Odaira, Rei and Gaudet, Matthew and Michael, Maged M. and Tomari, Hisanobu , title =. SIGARCH Comput. Archit. News , issue_date =. 2015 , issn =. doi:10.1145/2872887.2750403 , acmid =

    work page doi:10.1145/2872887.2750403 2015

  4. [4]

    Principles of Distributed Systems , pages=

    A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention , author=. Principles of Distributed Systems , pages=. 2013 , publisher=

    2013

  5. [5]

    A Simple Deterministic Algorithm for Guaranteeing the Forward Progress of Transactions , author=

  6. [6]

    Concurrent maintenance of skip lists , author=

  7. [7]

    Harris and Keir Fraser and Ian A

    Timothy L. Harris and Keir Fraser and Ian A. Pratt , title =. Distributed Computing, 16th International Conference,. 2002 , crossref =. doi:10.1007/3-540-36108-1_18 , timestamp =

    work page doi:10.1007/3-540-36108-1_18 2002

  8. [8]

    2002 , isbn =

    Distributed Computing, 16th International Conference,. 2002 , isbn =

    2002

  9. [9]

    Distributed Computing , pages=

    Transactional locking II , author=. Distributed Computing , pages=. 2006 , publisher=

    2006

  10. [10]

    and Scott, Michael L

    Michael, Maged M. and Scott, Michael L. , title =. Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing , series =. 1996 , isbn =. doi:10.1145/248052.248106 , acmid =

    work page doi:10.1145/248052.248106 1996

  11. [11]

    Distributed computing , volume=

    Fast and scalable rendezvousing , author=. Distributed computing , volume=. 2013 , publisher=

    2013

  12. [12]

    R. M. Karp and Y. Zhang. Parallel Algorithms for Backtrack Search and Branch-and-Bound

  13. [13]

    and Kirsch, Christoph M

    Henzinger, Thomas A. and Kirsch, Christoph M. and Payer, Hannes and Sezgin, Ali and Sokolova, Ana , title =. Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages , series =. 2013 , isbn =. doi:10.1145/2429069.2429109 , acmid =

    work page doi:10.1145/2429069.2429109 2013

  14. [14]

    Deo and S

    N. Deo and S. Prasad. Parallel Heap: An Optimal Parallel Priority Queue. The Journal of Supercomputing. 1992

    1992

  15. [15]

    BMC Systems Biology , volume =

    Brian Drawert and Stefan Engblom and Andreas Hellander , title =. BMC Systems Biology , volume =

  16. [16]

    A Parallel Priority Queue with Constant Time Operations , journal =

    Gerth St. A Parallel Priority Queue with Constant Time Operations , journal =. 1998 , volume =. doi:10.1006/jpdc.1998.1425 , timestamp =

    work page doi:10.1006/jpdc.1998.1425 1998

  17. [17]

    R. K. Treiber , title =. 1986 , number =

    1986

  18. [18]

    Inferential Queueing and Speculative Push for Reducing Critical Communication Latencies , booktitle =

    Rajwar, Ravi and K\". Inferential Queueing and Speculative Push for Reducing Critical Communication Latencies , booktitle =. 2003 , isbn =. doi:10.1145/782814.782853 , acmid =

    work page doi:10.1145/782814.782853 2003

  19. [19]

    and Vernon, Mary K

    Goodman, James R. and Vernon, Mary K. and Woest, Philip J. , title =. SIGARCH Comput. Archit. News , issue_date =. 1989 , issn =. doi:10.1145/68182.68188 , acmid =

    work page doi:10.1145/68182.68188 1989

  20. [20]

    Efficient Synchronization: Let Them Eat QOLB , journal =

    K\". Efficient Synchronization: Let Them Eat QOLB , journal =. 1997 , issn =. doi:10.1145/384286.264166 , acmid =

    work page doi:10.1145/384286.264166 1997

  21. [21]

    and Shavit, Nir , title =

    Dice, David and Marathe, Virendra J. and Shavit, Nir , title =. ACM Trans. Parallel Comput. , issue_date =. 2015 , issn =. doi:10.1145/2686884 , acmid =

    work page doi:10.1145/2686884 2015

  22. [22]

    1994 , institution=

    Building FIFO and priorityqueuing spin locks from atomic swap , author=. 1994 , institution=

    1994

  23. [23]

    Parallel Processing Symposium, 1994

    Queue locks on cache coherent multiprocessors , author=. Parallel Processing Symposium, 1994. Proceedings., Eighth International , pages=. 1994 , organization=

    1994

  24. [24]

    and Scott, Michael L

    Mellor-Crummey, John M. and Scott, Michael L. , title =. SIGPLAN Not. , issue_date =. 1991 , issn =. doi:10.1145/106973.106999 , acmid =

    work page doi:10.1145/106973.106999 1991

  25. [25]

    P. Sanders. Randomized Priority Queues for Fast Parallel Access. Journal Parallel and Distributed Computing, Special Issue on Parallel and Distributed Data Structures

  26. [26]

    TARDIS: Timestamp based Coherence Algorithm for Distributed Shared Memory

    TARDIS: Timestamp based Coherence Algorithm for Distributed Shared Memory , author=. arXiv preprint arXiv:1501.04504 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  27. [27]

    Scott , title =

    Michael L. Scott , title =. Shared-Memory Synchronization , series =. 2013 , url =. doi:10.2200/S00499ED1V01Y201304CAC023 , isbn =

    work page doi:10.2200/s00499ed1v01y201304cac023 2013

  28. [28]

    , title =

    Rajwar, Ravi and Goodman, James R. , title =. Proceedings of the 34th Annual ACM/IEEE International Symposium on Microarchitecture , series =. 2001 , isbn =

    2001

  29. [29]

    Parallel Architectures and Compilation Techniques (PACT), 2011 International Conference on , pages=

    DeNovo: Rethinking the memory hierarchy for disciplined parallelism , author=. Parallel Architectures and Compilation Techniques (PACT), 2011 International Conference on , pages=. 2011 , organization=

    2011

  30. [31]

    Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles , series =

    Nguyen, Donald and Lenharth, Andrew and Pingali, Keshav , title =. Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles , series =. 2013 , isbn =. doi:10.1145/2517349.2522739 , acmid =

    work page doi:10.1145/2517349.2522739 2013

  31. [32]

    Distributed Computing , volume =

    Yehuda Afek and Michael Hakimi and Adam Morrison , title =. Distributed Computing , volume =. 2013 , pages =

    2013

  32. [33]

    2001 , publisher=

    Introduction to algorithms , author=. 2001 , publisher=

    2001

  33. [34]

    and Hill, Mark D

    Sorin, Daniel J. and Hill, Mark D. and Wood, David A. , title =. 2011 , isbn =

    2011

  34. [35]

    Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures , series =

    Moir, Mark and Nussbaum, Daniel and Shalev, Ori and Shavit, Nir , title =. Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures , series =. 2005 , isbn =. doi:10.1145/1073970.1074013 , acmid =

    work page doi:10.1145/1073970.1074013 2005

  35. [36]

    and Tomari, Hisanobu , title =

    Nakaike, Takuya and Odaira, Rei and Gaudet, Matthew and Michael, Maged M. and Tomari, Hisanobu , title =. Proceedings of the 42Nd Annual International Symposium on Computer Architecture , series =. 2015 , isbn =. doi:10.1145/2749469.2750403 , acmid =

    work page doi:10.1145/2749469.2750403 2015

  36. [37]

    Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures , pages=

    High performance dynamic lock-free hash tables and list-based sets , author=. Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures , pages=. 2002 , organization=

    2002

  37. [38]

    ACM SIGPLAN Notices , volume=

    Practical concurrent binary search trees via logical ordering , author=. ACM SIGPLAN Notices , volume=. 2014 , organization=

    2014

  38. [40]

    Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing , series =

    Ellen, Faith and Fatourou, Panagiota and Ruppert, Eric and van Breugel, Franck , title =. Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing , series =. 2010 , isbn =. doi:10.1145/1835698.1835736 , acmid =

    work page doi:10.1145/1835698.1835736 2010

  39. [41]

    Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , series =

    Alistarh, Dan and Kopinsky, Justin and Li, Jerry and Shavit, Nir , title =. Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , series =. 2015 , isbn =. doi:10.1145/2688500.2688523 , acmid =

    work page doi:10.1145/2688500.2688523 2015

  40. [42]

    Distributed Computing , pages=

    Hopscotch hashing , author=. Distributed Computing , pages=. 2008 , publisher=

    2008

  41. [43]

    Parallel and Distributed Processing Symposium, 2000

    Skiplist-based concurrent priority queues , author=. Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International , pages=. 2000 , organization=

    2000

  42. [44]

    2004 , school=

    Practical lock-freedom , author=. 2004 , school=

    2004

  43. [45]

    Communications of the ACM , volume=

    Skip lists: a probabilistic alternative to balanced trees , author=. Communications of the ACM , volume=. 1990 , publisher=

    1990

  44. [46]

    High-Performance Computer Architecture, 2000

    Improving the throughput of synchronization by insertion of delays , author=. High-Performance Computer Architecture, 2000. HPCA-6. Proceedings. Sixth International Symposium on , pages=. 2000 , organization=

    2000

  45. [47]

    2005 , source =

    Shalev, Ori and Shavit, Nir , title =. 2005 , source =

    2005

  46. [48]

    Li and Ryan McElroy and Mike Paleczny and Daniel Peek and Paul Saab and David Stafford and Tony Tung and Venkateshwaran Venkataramani , title =

    Rajesh Nishtala and Hans Fugal and Steven Grimm and Marc Kwiatkowski and Herman Lee and Harry C. Li and Ryan McElroy and Mike Paleczny and Daniel Peek and Paul Saab and David Stafford and Tony Tung and Venkateshwaran Venkataramani , title =. Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) , year =

  47. [49]

    High Performance Computer Architecture (HPCA), 2010 IEEE 16th International Symposium on , pages=

    Graphite: A distributed parallel simulator for multicores , author=. High Performance Computer Architecture (HPCA), 2010 IEEE 16th International Symposium on , pages=. 2010 , organization=

    2010

  48. [50]

    ACM SIGPLAN Notices , volume=

    Quantitative relaxation of concurrent data structures , author=. ACM SIGPLAN Notices , volume=. 2013 , organization=

    2013

  49. [51]

    Journal of Parallel and Distributed Computing , volume=

    Fast and lock-free concurrent priority queues for multi-thread systems , author=. Journal of Parallel and Distributed Computing , volume=. 2005 , publisher=

    2005

  50. [52]

    ACM SIGPLAN Notices , volume=

    A speculation-friendly binary search tree , author=. ACM SIGPLAN Notices , volume=. 2012 , publisher=

    2012

  51. [53]

    25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada , year =

    Dave Dice and Yossi Lev and Mark Moir , title =. 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada , year =

  52. [54]

    , title =

    Harris, Timothy L. , title =. Proceedings of the 15th International Conference on Distributed Computing , series =. 2001 , isbn =

    2001

  53. [55]

    Proceedings of the 25th International Conference on Distributed Computing , series =

    Basin, Dmitry and Fan, Rui and Keidar, Idit and Kiselov, Ofer and Perelman, Dmitri , title =. Proceedings of the 25th International Conference on Distributed Computing , series =. 2011 , isbn =

    2011

  54. [56]

    Proceedings of the 22nd International Symposium on Distributed Computing, DISC 2008, Arcachon, France , year =

    Maurice Herlihy and Nir Shavit and Moran Tzafrir , title =. Proceedings of the 22nd International Symposium on Distributed Computing, DISC 2008, Arcachon, France , year =

    2008

  55. [57]

    Erez Petrank and Shahar Timnat , title =

  56. [58]

    24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, Pittsburgh, PA, USA , year =

    Anastasia Braginsky and Erez Petrank , title =. 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, Pittsburgh, PA, USA , year =

  57. [59]

    Faith Ellen and Danny Hendler and Nir Shavit , title =. SIAM J. Comput. , volume =. 2012 , pages =

    2012

  58. [60]

    and Cederman, D

    Wimmer, M. and Cederman, D. and Versaci, F. and Tr. Data Structures for Task-based Priority Scheduling , booktitle =

  59. [61]

    Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures , pages=

    Elimination trees and the construction of pools and stacks: preliminary version , author=. Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures , pages=. 1995 , organization=

    1995

  60. [62]

    and Gruber J

    Wimmer, M. and Gruber J. and Tr. The Lock-Free k-LSM Relaxed Priority Queue , booktitle =

  61. [63]

    52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

    Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui , title =. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

  62. [64]

    Journal of the ACM (JACM) , volume=

    Tight bounds for asynchronous renaming , author=. Journal of the ACM (JACM) , volume=. 2014 , publisher=

    2014

  63. [65]

    Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures , pages=

    Flat combining and the synchronization-parallelism tradeoff , author=. Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures , pages=. 2010 , organization=

    2010

  64. [66]

    Proceedings of the 1st ACM symposium on Cloud computing , pages=

    Benchmarking cloud serving systems with YCSB , author=. Proceedings of the 1st ACM symposium on Cloud computing , pages=

  65. [67]

    2017 , school=

    Techniques for Constructing Efficient Data Structures , author=. 2017 , school=

    2017

  66. [68]

    ACM Sigmod Record , volume=

    New TPC benchmarks for decision support and web commerce , author=. ACM Sigmod Record , volume=. 2000 , publisher=

    2000

  67. [69]

    ArXiv e-prints , archivePrefix = "arXiv", eprint =

    The Adaptive Priority Queue with Elimination and Combining. ArXiv e-prints , archivePrefix = "arXiv", eprint =

  68. [70]

    Nir Shavit , title =. Commun. ACM , volume =. 2011 , pages =

    2011

  69. [71]

    Stanford Large Network Dataset Collection , howpublished =

  70. [72]

    Dan Alistarh and Justin Kopinsky and Jerry Li and Nir Shavit , title =

  71. [73]

    Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , pages=

    The SprayList: A scalable relaxed priority queue , author=. Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , pages=. 2015 , organization=

    2015

  72. [74]

    ACM SIGPLAN Notices , volume=

    Fast concurrent queues for x86 processors , author=. ACM SIGPLAN Notices , volume=. 2013 , organization=

    2013

  73. [75]

    Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures , pages=

    A highly-efficient wait-free universal construction , author=. Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures , pages=. 2011 , organization=

    2011

  74. [76]

    Euro-Par 2013 Parallel Processing , pages=

    Lightweight contention management for efficient compare-and-swap operations , author=. Euro-Par 2013 Parallel Processing , pages=. 2013 , publisher=

    2013

  75. [77]

    Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems , pages=

    Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures , author=. Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems , pages=. 2015 , organization=

    2015

  76. [78]

    The SprayList: A Scalable Relaxed Priority Queue , url =

    Dan Alistarh and Justin Kopinsky and Jerry Li and Nir Shavit , month =. The SprayList: A Scalable Relaxed Priority Queue , url =

  77. [79]

    Workload Characterization (IISWC), 2015 IEEE International Symposium on , pages=

    CRONO: A Benchmark Suite for Multithreaded Graph Algorithms Executing on Futuristic Multicores , author=. Workload Characterization (IISWC), 2015 IEEE International Symposium on , pages=. 2015 , organization=

    2015

  78. [80]

    Workshop on Transactional Memory Workloads , volume=

    Early release: Friend or foe , author=. Workshop on Transactional Memory Workloads , volume=

  79. [81]

    Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , series =

    Guerraoui, Rachid and Trigonakis, Vasileios , title =. Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , series =. 2016 , isbn =. doi:10.1145/2851141.2851146 , acmid =

    work page doi:10.1145/2851141.2851146 2016

  80. [82]

    2013 , crossref =

    Trevor Brown and Faith Ellen and Eric Ruppert , title =. 2013 , crossref =. doi:10.1145/2484239.2484273 , timestamp =

    work page doi:10.1145/2484239.2484273 2013

Showing first 80 references.