Parallel Finger Search Structures

Seth Gilbert; Wei Quan Lim

REVIEW 1 major objections 5 minor 38 references

Parallel Finger Search Structures

T0 review · 1 major / 5 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 This paper presents two parallel finger search structures, FS1 and FS2, and claims they are the first to be work-optimal with respect to the finger bound while keeping parallelism within a polylogarithmic factor of optimal.

desk verdict First work-optimal parallel finger structure with polylog parallelism overhead; the central claims likely hold, but the unproved batch-parallel map from a self-cited companion paper is a genuine load-bearing dependency. read the letter →

arxiv 1908.02741 v4 pith:TQPCONPM submitted 2019-08-07 cs.DS cs.DC

Seth Gilbert , Wei Quan Lim This is my paper · ORCID

classification cs.DScs.DC

keywords parallelfingersearchstructureboundimplicitbatchingmultithreadingdictionarydistribution-sensitivealgorithmsbatch-parallelmappipelining

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

This paper sets out to give the first parallel finger search structure: a dictionary that, like a sequential finger tree, charges less for operations near designated fingers, but now runs on $p$ processors. The central claim is that both versions, FS1 and FS2, are work-optimal with respect to the finger bound: over any sequence of operations, the total work is $O(F_L)$, where $F_L = \sum_i(\log r_i+1)$ and $r_i$ is the finger distance of the $i$-th call in some linearization $L$ of the program's calls. At the same time, the parallelism overhead is small: running a program on $p$ processors takes roughly $(T_1+F_L)/p + T_\infty$ plus a term that is polylogarithmic in $p$ per data-structure call along a path. If the bounds hold, programmers can use a finger search structure as a black box inside multithreaded programs, inheriting local-access speedups without serializing on the data structure.

What carries the argument

The load-bearing object is the segmented structure with doubly exponential segment sizes. Items are kept in two chains, front and back, with segment $\mathrm{Si}[k]$ a balanced tree of size around $2\cdot c(k)$, where $c(k)=2^{2^{k+1}}$; the first $\Theta(\log\log n)$ segments contain all items very close to a finger. Operations are processed in batches: a preliminary unsorted search of the small segments eliminates ineffectual operations cheaply, residual operations are entropy-sorted and executed as sorted batches on each segment, and rebalancing shifts items between neighbouring segments with a credit invariant that makes all rebalancing $O(1)$ amortized per operation. FS2's extra machinery is an odd-even neighbour-lock pipeline on the larger segments, with a deferral rule that keeps segments balanced and a delay-charging argument bounding the deferment time by $O(N/p)$.

What would settle it

Fix a batch of $b$ insertions and $b$ deletions all targeting the smallest segment, run FS1 on one processor, and instrument the credit invariant: a segment holding $q$ items beyond its target must hold at least $q\cdot 2^{-k}$ credits. If any segment is found with fewer credits, or if total work on such batches grows faster than $O(b)$, the amortized finger-bound claim is false.

Watch

Extended reading notes

Core claim

The paper's discovery is that the sequential finger property can be preserved under parallel batching. Its construction FS0 stores the ordered items in two chains of segments whose sizes grow doubly exponentially, $c(k)=2^{2^{k+1}}$; an access at finger distance $r$ lands in a segment of index about $\log\log r$, so searching costs $O(\log r+1)$. FS1 turns FS0 into a batch-parallel structure by filtering each batch through the small segments unsorted, entropy-sorting only the surviving residual operations, and executing them segment by segment; rebalancing is paid for by a stored-credit invariant, $q\cdot 2^{-k}$ credits for a segment $q$ items beyond its target size, giving $O(F_L)$ total work. FS2 adds a pipeline over the larger segments, with neighbour locks and a deferral mechanism, to shrink the data-structure span to $O(N/p + d(\log p)^2 + s_L)$. The results are stated for any program modelled by a DAG and any greedy scheduler, with the guarantee expressed through some linearization $L$ of the data-structure calls consistent with the results. The authors also sketch an extension to a fixed number of movable fingers by concatenating sector-wise basic finger structures.

Load-bearing premise

The argument assumes the batch-parallel dictionary that stores each segment actually performs a batch of $b$ searches in $O(b\log n)$ work with the stated span; these primitives come from a companion paper and are not proved here, so any error in them would invalidate the finger-bound and running-time theorems.

Editorial extensions

If this is right

If the work bound holds, a program whose calls to FS1 are spread over $p$ processors finishes in $O((T_1+F_L)/p + T_\infty + d((\log p)^2+\log n))$ time, so the structure adds no more than a polylogarithmic penalty per call along a critical path.
Operations on items close to a finger keep their sequential advantage: an access at finger distance $r$ costs $O(\log r+1)$ amortized work, so local workloads cost far less than $\log n$ per operation.
FS2's pipelining reduces the per-call span penalty to $O((\log p)^2)$ plus the weighted span $s_L$, meaning expensive far-away accesses no longer hold up later batches except through their own finger cost.
The same framework supports any fixed number $f$ of movable fingers by concatenating $f+1$ basic finger structures, preserving the finger-bound work and the parallelism bounds.
The work and span bounds compose with other implicitly batched data structures under greedy scheduling, so the structure can be used as a black box inside a larger multithreaded program.

Reading between the lines

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

If the cited batch-parallel map delivers its stated costs, the same segmented skeleton might be reused to parallelize other distribution-sensitive structures, such as a splay-tree-like structure with both working-set and finger properties, which the paper itself raises as an open question.
A testable consequence not checked in the paper: on workloads with strong locality, FS2 should show speedup scaling with $p$ on clustered insertions and deletions, while random far-apart accesses should approach ordinary balanced-tree costs; this could be benchmarked against batch-parallel balanced trees.
The guarantee is existential over a chosen linearization $L$ of calls consistent with the results, so an adversary who forces widely separated accesses in every linearization will face costs closer to the balanced-tree bound rather than the finger bound.
Because the credit invariant is tied to segment sizes rather than the internal map, replacing the 2-3 tree inside each segment with another batch-parallel map should preserve the amortized bounds, enabling cache-optimized or footprint-optimized variants.

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.

Desk Editor's Note

read the letter

Funny thing: this is the first parallel finger search structure that nails the finger bound in work with polylog parallelism overhead, and the design is genuinely clever. FS0's double-exponential segments with credit-based rebalancing is a neat simplification; FS1's trick of filtering through a small first slab before entropy-sorting avoids paying log b per nearby access; FS2's pipelined final slab with deferral and odd-even locks is a serious piece of algorithmic engineering. The main theorems state clean composable bounds, and the amortized segment arguments (Lemmas 8, 13, 17) look coherent to me.

The soft spots are real but narrow. The whole structure is built on a batch-parallel map imported from [28], a self-cited arXiv preprint. The map's bounds (unsorted batch search, sorted batch access, split/join) are stated in Appendix A.3 but not proved here, and every segment stores its items in such a map. If any of those bounds has a hidden log factor, the finger-bound claim leaks through every segment. That's an omitted proof, not a demonstrated error, but it is load-bearing. Any referee report should dig into [28] or ask the authors to include the proofs.

The linearization issue the reader flagged is, I think, less severe. In Theorem 12 the work is O(max(FL*, FL')). Since both L* and L' are valid linearizations, whichever term dominates gives a linearization whose finger bound matches the work bound. So the 'for some L' claim survives; it just isn't explained well. Similarly for FS2.

The FS2 section is dense, and the invariants in Lemma 15 are plausible but hard to verify quickly. The movable-finger generalization is explicitly sketched rather than fully proved, which is fine for a paper this size but should be stated as a limitation.

Who is this for? People working on parallel data structure theory, especially implicit batching and batch-parallel ordered sets. No experiments, none needed. Deserves a serious referee: if the [28] dependency checks out, the main claims are likely correct. I'd accept it for review and ask for a filled-in proof of the batch-map primitives or a clear pointer to a published version.

Referee Report

1 major / 5 minor

Summary. The manuscript presents two parallel finger search structures, FS1 and FS2, in the QRMW pointer-machine model. FS1 processes implicit-batching input batches one at a time, filtering operations through a small first slab by unsorted search before entropy-sorting the remaining operations; FS2 additionally pipelines the final slab using bounded buffers, a feed-buffer of cut batches, and an odd-even neighbour-lock scheme. The paper claims that, for some linearization L of the data-structure calls, each structure performs O(F_L) total work, where F_L is the finger bound, with span O(N/p + d((log p)^2 + log n)) for FS1 and O(N/p + d(log p)^2 + s_L) for FS2, and derives the corresponding end-to-end running times for programs running on a greedy scheduler. The paper also sketches extensions to movable fingers and to work-stealing schedulers. The main technical content is a set of amortized credit arguments for the doubly-exponential segmented layout and a modular cost accounting that separates data-structure work and span from scheduler overhead.

Significance. Modulo the unproved batch-parallel map bounds imported from the companion paper [28], the contribution is substantial. This appears to be the first parallel finger search structure that is work-optimal with respect to the finger bound while maintaining polylogarithmic span overhead, and the modular treatment within the extended implicit batching framework makes the result composable with other data structures. The amortized segment analyses (Lemmas 8, 13, 17) and the span-accounting structure are coherent and clearly presented, and the paper is careful about the computation model, including contention costs. The paper is a purely theoretical analysis; no experimental validation is claimed. The main weakness is self-containment: the central theorems inherit all of their per-segment operation costs from [28], a self-cited arXiv preprint whose results are not proved here. If those bounds are correct and are supplied, the paper meets the bar for a strong theory contribution.

major comments (1)

[Appendix A.3 (batch-parallel map); used in Sections 4.1 and 5.1] The batch-parallel map bounds are load-bearing and are not proved in this manuscript. Every segment of FS1 and FS2 is stored in a batch-parallel map, and each batch is processed through unsorted batch search, sorted batch access, split and join; Theorems 12, 14, 16 and 21 count these operations as O(b log c(k)) work and O(log b + log c(k)) or O(log b log c(k)) span and then sum these costs to obtain the central O(F_L) work bound and the span bounds. Appendix A.3 states only that these bounds 'can be achieved in the QRMW pointer machine model [28]', where [28] is a self-cited arXiv preprint, and no proof or exact companion-theorem reference is supplied. If the companion map has an extra logarithmic factor, a hidden batch-size restriction, or a hidden dependence on duplicate items, that error propagates directly into every main theorem. Please include a complete proof of the four map primitives, or state and prove the exact theorems of [28] on which the paper relies, so that the central claim is verifiable from this manuscript alone.

minor comments (5)

[Theorem 12 / Theorem 16 (proofs)] The proofs bound part of the work by F_{L'} and part by F_{L*} and conclude O(max(F_{L*}, F_{L'})); it would be clearer to state explicitly that since max(F_{L*}, F_{L'}) is O(F_L) when L is chosen to be the linearization with the larger finger bound, the theorem's single-linearization form follows. As written, the reader must supply this step.
[Theorem 21 (FS2 Span)] The sentence 'over all X, each of b, b′, g, i·p2, j·p2 above will sum up to at most the total number N of FS2-calls' is not justified in the text. Because the span bound's O(N/p) term rests on it, please give the charging argument explicitly, in particular why a queued cut batch is charged only once along a given path and why a path contains at most one call from each input batch.
[Section 4.1 and Figure 2] The definition of m is inconsistent: the text says m = ⌈log log(2b)⌉ + 1 while Figure 2 labels the first slab with m = ⌈log log(2b)⌉. Please align the notation.
[Section 7] The adaptation to work-stealing schedulers is only sketched; for the claim that the bounds hold on average under a work-stealing scheduler, please provide at least a proof outline with the key lemmas, or explicitly label the section as non-rigorous.
[Appendix A.3] The sorted batch access primitive is specified as O(b log n) work and O(log b + log n) span; it would help to state whether duplicate keys are allowed in the batch and how they are resolved, since the main text uses the primitive after combining duplicates into group-operations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the finger-structure theorems depend on the companion batch-parallel map [28], but that map is a parameter-free external component whose stated costs do not encode the finger bound.

full rationale

The derivation is modular rather than circular. Section 4.1 says 'The items in each segment are stored in a batch-parallel map (Appendix Section A.3)', and Appendix A.3 states 'This can be achieved in the QRMW pointer machine model [28]'. These map costs enter Theorems 12, 14, 16, and 21 as per-segment operation costs, but [28] (Lim, arXiv:1905.05254) is a companion paper on batch-parallel 2-3 trees whose stated guarantees (O(b log n) work for unsorted batch search, O(b log n) for sorted batch access, and O(log n) for split/join) are parameter-free, are stated for a model that does not include the present finger bound, and are not derived from the finger structure. Invoking [28] is therefore a standard modular reduction, not a self-referential one. No fitted parameter is renamed as a prediction, no uniqueness theorem or ansatz is imported from the authors' prior work, and the amortized credit arguments and pipelining analysis are carried out in the text. The fact that [28] is not re-proved here is a completeness and correctness-risk concern, not circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 3 invented entities

The central claims rest on three categories of unproved-in-this-paper inputs: (1) the batch-parallel map costs from the self-cited [28], (2) the extended implicit batching buffer guarantees from [4], and (3) the QRMW model primitives. The hand-chosen segment-size and slab-threshold parameters are design decisions that the proofs depend on but that are not forced by any external benchmark. There are no empirically fitted constants.

free parameters (4)

Segment size function c(k) = c(k) = 2^(2^k+1)
Double-exponential segment growth is chosen by hand so that searching through the first k segments costs O(2^k) = O(log r) for finger distance r, and so that rebalancing cascades amortize. It is a design parameter, not derived from prior constraints.
First slab length m = m = ceil(log log(5p^2)) for FS2; m = ceil(log log(2b))+1 for FS1
The threshold separating cheap near-end sections from the rest is chosen so that m is about log log(p^2), making preliminary and separation phases take O((log p)^2) span while keeping the residual batch large enough for sorting bounds.
FS2 cut batch size = p^2
Batches are cut to at most p^2 operations to bound sorting span by O((log p)^2) and to make delay-per-batch O(p) so deferments can be paid for by work/p.
Balance slack constants = target t(k)=2c(k); balance range [c(k), 3c(k)] roughly
The allowed segment size range is chosen so that each segment remains at least half full and at most double target, which the credit invariant and the final-slab underfull arguments rely on.

assumptions (4)

ad hoc to paper The batch-parallel map of [28] supports unsorted batch search and sorted batch access with the stated work/span in the QRMW pointer machine model.
Invoked at Section 4.1 and Appendix A.3; the current paper does not prove these costs and [28] is a self-cited preprint by co-author Lim. This is the main external load-bearing assumption.
domain assumption The extended implicit batching framework [4] provides a parallel buffer with the properties needed for Theorem 24 (buffer cost O((T1+w)/p + d log p)).
Section 2 and Appendix A.4 rely on [4]'s framework; the paper reproduces Theorem 24's proof but the buffer construction is largely from [4].
domain assumption The QRMW pointer machine model and the parallel primitives (fork/join, suspend/resume, non-blocking and dedicated locks, reactivation wrapper) have the stated O(1) time and fairness guarantees.
Sections 2.1 and Appendix A.6 define these primitives and give pseudocode; the performance bounds assume these implementations behave as claimed under FIFO RMW contention.
standard math Comparison-based sorting lower bound (Lemma 25, from Munro and Spira [30]) and the maximum finger bound relation (Theorem 28).
Used to justify that entropy-sorting work is absorbed by the finger bound; cited to [30].

invented entities (3)

Deferred flag per section
purpose: Marks that a section's run is postponed until its neighbour finishes, enabling FS2's pipelined deferment accounting.
Introduced in Section 5.1; exists only as an algorithmic device within the paper, no external falsifiable handle.
Feed buffer of bunches
purpose: Queues cut batches of size p^2 between the parallel buffer and the first slab in FS2 to bound batch sizes and delays.
Section 5.1; internal algorithmic component.
Neighbour-lock odd-even locking scheme
purpose: Coordinates pipelined access between adjacent final-slab sections so that a section does not read or modify its neighbours while they are mid-run.
Section 5.1 and Figure 3; internal concurrency device.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Parallel Finger Search Structures." pith.science (2026). https://pith.science/paper/TQPCONPM

@misc{pith2026190802741,
  author       = {Pith},
  title        = {Pith review of: Parallel Finger Search Structures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TQPCONPM}},
  note         = {Machine review of arXiv:1908.02741}
}

read the original abstract

In this paper we present two versions of a parallel finger structure FS on p processors that supports searches, insertions and deletions, and has a finger at each end. This is to our knowledge the first implementation of a parallel search structure that is work-optimal with respect to the finger bound and yet has very good parallelism (within a factor of O( (log p)^2 ) of optimal). We utilize an extended implicit batching framework that transparently facilitates the use of FS by any parallel program P that is modelled by a dynamically generated DAG D where each node is either a unit-time instruction or a call to FS. The total work done by either version of FS is bounded by the finger bound F[L] (for some linearization L of D ), i.e. each operation on an item with finger distance r takes O( log r + 1 ) amortized work; it is cheaper for items closer to a finger. Running P using the simpler version takes O( ( T[1] + F[L] ) / p + T[inf] + d * ( (log p)^2 + log n ) ) time on a greedy scheduler, where T[1],T[inf] are the size and span of D respectively, and n is the maximum number of items in FS, and d is the maximum number of calls to FS along any path in D. Using the faster version, this is reduced to O( ( T[1] + F[L] ) / p + T[inf] + d * (log p)^2 + s[L] ) time, where s[L] is the weighted span of D where each call to FS is weighted by its cost according to F[L]. We also sketch how to extend FS to support a fixed number of movable fingers. The data structures in our paper fit into the dynamic multithreading paradigm, and their performance bounds are directly composable with other data structures given in the same paradigm. Also, the results can be translated to practical implementations using work-stealing schedulers.

Figures

Figures reproduced from arXiv: 1908.02741 by the authors.

**Figure 1.** FS0 Outline; each box Si [k] represents a 2-3 tree of size Θ(2 2 k ) for k < l FS0 keeps the items in order in two halves, the front half stored in a chain of segments S0 [0..l], and the back half stored in reverse order in a chain of segments S1 [0..l]. Let c(k) = 2 2 k+1 for each k ∈ Z. Each segment Si [k] has a target size t(k) = 2·c(k), and a target capacity defined to be [t(k),t(k)] if k < l but [0,t(k)] if k =… view at source ↗

**Figure 2.** FS1 Outline; each batch is sorted only after being filtered through the smaller sections FS1 -calls are put into the parallel buffer (Section 2) for FS1 . Whenever the previous batch is done, FS1 flushes the parallel buffer to obtain the next batch B. Let b be the size of B, and we can assume b > 1. Based on b, the sections in FS1 are conceptually divided into two slabs, the first slab comprising sections S[0..m−1] … view at source ↗

**Figure 3.** FS2 Sketch; the final slab is pipelined, facilitated by locks between adjacent sections We shall now give the details (see [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 37 canonical work pages

[28]

Optimal Multithreaded Batch-Parallel 2-3 Trees

Wei Quan Lim. Optimal multithreaded batch-parallel 2-3 trees. arXiv:1905.05254, 2019

work page Pith review arXiv 1905
[1]

The cb tree: a practical concurrent self-adjusting search tree

Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E Tarjan. The cb tree: a practical concurrent self-adjusting search tree. Distributed computing, 27(6):393–417, 2014

work page 2014
[2]

Cbtree: A practical concurrent self-adjusting search tree

Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert Endre Tarjan. Cbtree: A practical concurrent self-adjusting search tree. In DISC, volume 7611 of Lecture Notes in Computer Science, pages 1–15. Springer, 2012

work page 2012
[3]

Provably good scheduling for parallel programs that use data structures through implicit batching

Kunal Agrawal, Jeremy T Fineman, Kefu Lu, Brendan Sheridan, Jim Sukha, and Robert Utterback. Provably good scheduling for parallel programs that use data structures through implicit batching. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, pages 84–95. ACM, 2014

work page 2014
[4]

Parallel working-set search structures

Kunal Agrawal, Seth Gilbert, and Wei Quan Lim. Parallel working-set search structures. In Proceedings of the 30th ACM symposium on Parallelism in algorithms and architectures, pages 321–332. ACM, 2018

work page 2018
[5]

Fast parallel operations on search trees

Yaroslav Akhremtsev and Peter Sanders. Fast parallel operations on search trees. In 2016 IEEE 23rd International Conference on High Performance Computing (HiPC), pages 291–300. IEEE, 2016

work page 2016
[6]

Parallel Combining: Beneﬁts of Explicit Synchronization

Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto. Parallel Combining: Beneﬁts of Explicit Synchronization. In Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira, editors, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:...

work page 2018
[7]

Thread scheduling for multiprogrammed multiprocessors.Theory of computing systems, 34(2):115–144, 2001

Nimar S Arora, Robert D Blumofe, and C Greg Plaxton. Thread scheduling for multiprogrammed multiprocessors.Theory of computing systems, 34(2):115–144, 2001

work page 2001

Show all 38 references

[8]

Just join for parallel ordered sets

Guy E Blelloch, Daniel Ferizovic, and Yihan Sun. Just join for parallel ordered sets. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 253–264. ACM, 2016

2016
[9]

Optimal parallel algorithms in the binary-forking model

Guy E Blelloch, Jeremy T Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. arXiv preprint arXiv:1903.04650, 2019

1903 arXiv
[10]

Blelloch and Margaret Reid-Miller

Guy E. Blelloch and Margaret Reid-Miller. Pipelining with futures. In Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, SPAA ’97, pages 249–259, New York, NY , USA, 1997. ACM

1997
[11]

Blelloch and Margaret Reid-Miller

Guy E. Blelloch and Margaret Reid-Miller. Fast set operations using treaps. In Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, pages 16–26, 1998

1998
[12]

Scheduling multithreaded computations by work stealing

Robert D Blumofe and Charles E Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM), 46(5):720–748, 1999

1999
[13]

A general technique for non-blocking trees

Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. In ACM SIGPLAN Notices, volume 49, pages 329–342. ACM, 2014

2014
[14]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, third edition, 2009

2009
[15]

Contention in shared memory algorithms.Journal of the ACM (JACM), 44(6):779–805, 1997

Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms.Journal of the ACM (JACM), 44(6):779–805, 1997

1997
[16]

The amortized complexity of non-blocking binary search trees

Faith Ellen, Panagiota Fatourou, Joanna Helga, and Eric Ruppert. The amortized complexity of non-blocking binary search trees. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 332–340. ACM, 2014

2014
[17]

Non-blocking binary search trees

Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pages 131–140, New York, NY , USA, 2010. ACM

2010
[18]

Parallel bi-objective shortest paths using weight-balanced b-trees with bulk updates

Stephan Erb, Moritz Kobitzsch, and Peter Sanders. Parallel bi-objective shortest paths using weight-balanced b-trees with bulk updates. In International Symposium on Experimental Algorithms, pages 111–122. Springer, 2014

2014
[19]

Kallimanis

Panagiota Fatourou and Nikolaos D. Kallimanis. Revisiting the combining synchronization technique. In PPoPP, pages 257–266, 2012

2012
[20]

Leiserson, and Keith H

Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. The implementation of the Cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 212–223, 1998

1998
[21]

Sorting on a parallel pointer machine with applications to set expression evaluation

Michael T Goodrich and S Rao Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation. Journal of the ACM (JACM), 43(2):331–361, 1996

1996
[22]

A new representation for linear lists

Leo J Guibas, Edward M McCreight, Michael F Plass, and Janet R Roberts. A new representation for linear lists. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 49–60. ACM, 1977. 22

1977
[23]

Flat combining and the synchronization-parallelism tradeoff

Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 355–364, 2010

2010
[24]

Alternatives to splay trees with O(log n) worst-case access times

John Iacono. Alternatives to splay trees with O(log n) worst-case access times. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 516–522. Society for Industrial and Applied Mathematics, 2001

2001
[25]

Intel Cilk Plus Language Extension Speciﬁcation, Version 1.1 , 2013

Intel Corporation. Intel Cilk Plus Language Extension Speciﬁcation, Version 1.1 , 2013. Document 324396- 002US. Available from http://cilkplus.org/sites/default/files/open_specifications/Intel_Cilk_ plus_lang_spec_2.htm

2013
[26]

An introduction to parallel algorithms, volume 17

Joseph JáJá. An introduction to parallel algorithms, volume 17. Addison-Wesley Reading, 1992

1992
[27]

Localized search in sorted lists

S Rao Kosaraju. Localized search in sorted lists. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, pages 62–69. ACM, 1981

1981
[29]

Queue locks on cache coherent multiprocessors

Peter Magnusson, Anders Landin, and Erik Hagersten. Queue locks on cache coherent multiprocessors. In Parallel Processing Symposium, 1994. Proceedings., Eighth International, pages 165–171. IEEE, 1994

1994
[30]

Sorting and searching in multisets

Ian Munro and Philip M Spira. Sorting and searching in multisets. SIAM journal on Computing, 5(1):1–8, 1976

1976
[31]

OpenMP application program interface, version 4.0

OpenMP Architecture Review Board. OpenMP application program interface, version 4.0. Available from http: //www.openmp.org/mp-documents/OpenMP4.0.0.pdf, July 2013

2013
[32]

Oyama, K

Y . Oyama, K. Taura, and A. Yonezawa. Executing parallel programs with synchronization bottlenecks efﬁciently. In Proceedings of the International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA), pages 182–204, 1999

1999
[33]

Parallel dictionaries on 2–3 trees

Wolfgang Paul, Uzi Vishkin, and Hubert Wagener. Parallel dictionaries on 2–3 trees. Automata, Languages and Programming, pages 597–609, 1983

1983
[34]

Intel Threading Building Blocks: Outﬁtting C++ for Multi-Core Processor Parallelism

James Reinders. Intel Threading Building Blocks: Outﬁtting C++ for Multi-Core Processor Parallelism. O’Reilly, 2007

2007
[35]

Ics 643: Advanced parallel algorithms lecture 10.http://www2.hawaii.edu/~nodari/teaching/ f16/notes/notes10.pdf, 2016

Nodari Sitchinava. Ics 643: Advanced parallel algorithms lecture 10.http://www2.hawaii.edu/~nodari/teaching/ f16/notes/notes10.pdf, 2016

2016
[36]

Self-adjusting binary search trees

Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM) , 32(3):652–686, 1985

1985
[37]

http://msdn.microsoft.com/en-us/magazine/cc163340.aspx, October 2007

The Task Parallel Library. http://msdn.microsoft.com/en-us/magazine/cc163340.aspx, October 2007

2007
[38]

Batch-parallel euler tour trees

Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. Batch-parallel euler tour trees. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 92–106. SIAM, 2019. 23

2019

Pith tools

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

[1] [28]

Optimal Multithreaded Batch-Parallel 2-3 Trees

Wei Quan Lim. Optimal multithreaded batch-parallel 2-3 trees. arXiv:1905.05254, 2019

work page Pith review arXiv 1905

[2] [1]

The cb tree: a practical concurrent self-adjusting search tree

Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E Tarjan. The cb tree: a practical concurrent self-adjusting search tree. Distributed computing, 27(6):393–417, 2014

work page 2014

[3] [2]

Cbtree: A practical concurrent self-adjusting search tree

Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert Endre Tarjan. Cbtree: A practical concurrent self-adjusting search tree. In DISC, volume 7611 of Lecture Notes in Computer Science, pages 1–15. Springer, 2012

work page 2012

[4] [3]

Provably good scheduling for parallel programs that use data structures through implicit batching

Kunal Agrawal, Jeremy T Fineman, Kefu Lu, Brendan Sheridan, Jim Sukha, and Robert Utterback. Provably good scheduling for parallel programs that use data structures through implicit batching. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, pages 84–95. ACM, 2014

work page 2014

[5] [4]

Parallel working-set search structures

Kunal Agrawal, Seth Gilbert, and Wei Quan Lim. Parallel working-set search structures. In Proceedings of the 30th ACM symposium on Parallelism in algorithms and architectures, pages 321–332. ACM, 2018

work page 2018

[6] [5]

Fast parallel operations on search trees

Yaroslav Akhremtsev and Peter Sanders. Fast parallel operations on search trees. In 2016 IEEE 23rd International Conference on High Performance Computing (HiPC), pages 291–300. IEEE, 2016

work page 2016

[7] [6]

Parallel Combining: Beneﬁts of Explicit Synchronization

Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto. Parallel Combining: Beneﬁts of Explicit Synchronization. In Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira, editors, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:...

work page 2018

[8] [7]

Thread scheduling for multiprogrammed multiprocessors.Theory of computing systems, 34(2):115–144, 2001

Nimar S Arora, Robert D Blumofe, and C Greg Plaxton. Thread scheduling for multiprogrammed multiprocessors.Theory of computing systems, 34(2):115–144, 2001

work page 2001