{"id":"3679789f-3fc1-43c8-885b-072457a3ba3e","arxiv_id":"1908.02741","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"First work-optimal parallel finger search structures, with the simpler FS1 and the faster pipelined FS2, both provably matching the sequential finger bound under a greedy scheduler.","lead":"This paper designs two parallel data structures, FS1 and FS2, that let many processors search, insert, and delete in a sorted map, with cheaper operations for items near the ends. They are the first parallel search structures whose total work matches the sequential finger-search bound while keeping scheduling overhead near polylogarithmic.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The work-optimality and span theorems all rest on batch-parallel map operations imported from the self-cited companion paper [28], which are stated without proof here; that is the load-bearing gap.","rationale":"The paper's central claim is that FS1/FS2 attain O(F_L) work for some linearization L. The proof architecture is: every segment is a batch-parallel map with prescribed work and span, and the finger bound is obtained by summing the per-segment costs. I checked the internal linearization and entropy-sorting steps (Theorem 12, Theorem 28, Theorem 32) and did not find a clear error: operations within a batch are mutually independent because a calling thread blocks until its FS call returns, so the chosen L* is a valid linearization, and the inward-distance argument for H_j in O(C_j) survives the tie cases. The remaining unproven link is the batch-parallel map itself, imported from the self-cited companion paper [28]. Section 4.1 and Appendix A.3 state the required operation bounds but give no proof, and every segment, every batch, and every rebalancing uses these operations. Therefore any error or omitted log factor in [28] directly invalidates Theorems 12, 14, 16, and 21. This is an omitted proof rather than a demonstrated falsehood, which is exactly the situation a CONDITIONAL verdict is designed for. I therefore agree with the reader and would not change the verdict.","tokens_in":29527,"tokens_out":19923,"duration_ms":227442,"concrete_test":"Independently re-derive from [28] the four batch-parallel map operation bounds (unsorted batch search in O(b log n) work and O(log b log n) span; sorted batch access in O(b log n) work and O(log b + log n) span; split and join in O(log n) work/span), and then re-run the proofs of Theorems 12, 14, 16, and 21 replacing the abstract map with that concrete implementation. If any of the per-segment costs is larger than assumed, the O(F_L) work bound is violated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"FS1 and FS2 store every segment in a 'batch-parallel map' (Section 4.1, Appendix A.3) and invoke unsorted batch search, sorted batch access, split, and join in every batch and at every segment. Theorems 12, 14, 16, and 21 count these as O(b log c(k)) work and O(log b + log c(k)) or O(log b log c(k)) span, and the final O(F_L) work and O(N/p + d((log p)^2 + log n)) span bounds are exactly the sums of these per-segment costs. Appendix A.3 does not prove the map bounds; it says only that they 'can be achieved in the QRMW pointer machine model [28]', where [28] is a self-cited arXiv preprint. No independent derivation or machine-checked proof is supplied. If the companion map's unsorted batch search, sorted batch access, split, or join have hidden costs (an extra log factor, a dependence on duplicate items, or a restriction on batch size), those costs propagate through every segment and the central finger-bound claim no longer follows. This is an omitted proof rather than a demonstrated contradiction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29813,"tokens_out":17644,"duration_ms":188555,"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":[{"comment":"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.","section":"Appendix A.3 (batch-parallel map); used in Sections 4.1 and 5.1"}],"minor_comments":[{"comment":"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.","section":"Theorem 12 / Theorem 16 (proofs)"},{"comment":"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":"Theorem 21 (FS2 Span)"},{"comment":"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":"Section 4.1 and Figure 2"},{"comment":"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.","section":"Section 7"},{"comment":"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.","section":"Appendix A.3"}],"recommendation":"major_revision","confidential_remarks":"Please check whether the companion paper [28] has undergone peer review; the submitted manuscript's central theorems depend on unproved bounds from that arXiv preprint. If [28] is available and correct, the authors should state exact theorem numbers and reproduce the relevant proofs in an appendix. I otherwise did not find evidence of unsoundness in the amortized segment analyses."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":30331,"tokens_out":2952,"would_cite":true,"duration_ms":32293,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["parallel finger search structure","finger bound","implicit batching","multithreading","dictionary","distribution-sensitive algorithms","batch-parallel map","pipelining"],"falsifier":"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.","tokens_in":29300,"feed_emoji":"🔍","tokens_out":9392,"duration_ms":97646,"temperature":0.7,"pith_summary":"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.","feed_headline":"Parallel finger search hits the finger bound with polylog overhead","feed_subtitle":"Nearby accesses keep their cost advantage while p processors share the work.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"This companion paper supplies the batch-parallel map primitives (unsorted batch search, sorted batch access, split, join) used inside every segment; the main theorems inherit their cost assumptions from here.","marker":"[28]"},{"why":"This is the source of the extended implicit batching framework and parallel buffer whose cost analysis converts the data-structure bounds into program running times.","marker":"[4]"},{"why":"It defines the sequential finger tree with the $O(\\log r + 1)$ finger bound that the paper aims to match in parallel.","marker":"[27]"},{"why":"It gives the earlier sequential finger structure whose staggered-rebalancing idea motivates the amortized segment structure FS0.","marker":"[22]"},{"why":"It introduces implicit batching, the base mechanism that the paper extends by allowing the data structure to flush batches independently and pipeline them.","marker":"[3]"},{"why":"It supplies the working-set structure whose doubly exponential layout inspires the segment size schedule $c(k)$ that makes the finger bound attainable.","marker":"[24]"}],"fun_headline_variants":["Parallel finger search matches sequential work bound","Batch-parallel finger search preserves locality","Finger search parallelized with polylog overhead","Work-optimal parallel finger search structure"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Parallel finger search matches sequential work bound","Batch-parallel finger search preserves locality","Finger search parallelized with polylog overhead","Work-optimal parallel finger search structure"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000483,"raw_usage":{"total_tokens":2502,"prompt_tokens":1179,"completion_tokens":1323,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":795,"completion_tokens_details":{"reasoning_tokens":1269}},"tokens_in":795,"tokens_out":1323,"duration_ms":11175,"temperature":1.0,"reasoning_tokens":1269,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:38:17.350260+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Optimal Multithreaded Batch-Parallel 2-3 Trees","cited_arxiv_id":"1905.05254","evidence_quote":"This companion paper supplies the batch-parallel map primitives (unsorted batch search, sorted batch access, split, join) used inside every segment; the main theorems inherit their cost assumptions from here."},{"cited_title":"Parallel working-set search structures","cited_arxiv_id":null,"evidence_quote":"This is the source of the extended implicit batching framework and parallel buffer whose cost analysis converts the data-structure bounds into program running times."},{"cited_title":"Localized search in sorted lists","cited_arxiv_id":null,"evidence_quote":"It defines the sequential finger tree with the $O(\\log r + 1)$ finger bound that the paper aims to match in parallel."},{"cited_title":"A new representation for linear lists","cited_arxiv_id":null,"evidence_quote":"It gives the earlier sequential finger structure whose staggered-rebalancing idea motivates the amortized segment structure FS0."},{"cited_title":"Provably good scheduling for parallel programs that use data structures through implicit batching","cited_arxiv_id":null,"evidence_quote":"It introduces implicit batching, the base mechanism that the paper extends by allowing the data structure to flush batches independently and pipeline them."},{"cited_title":"Alternatives to splay trees with O(log n) worst-case access times","cited_arxiv_id":null,"evidence_quote":"It supplies the working-set structure whose doubly exponential layout inspires the segment size schedule $c(k)$ that makes the finger bound attainable."}],"review_version":1}