Persistence overhead does not supply the current selector

Assessment 245, 13 October 2026. Combined primary-proof review and editorial pass. Construction 85 remains the latest native theorem. Preserved mathematical frontier; independent finite audit.

What the comparison resolves

A representation may preserve every answer yet still require a costly operation to select the answer belonging to the current version. Two primary arguments separate that selection cost from the cost of repairing persistent storage. Dietz builds a version-sensitive predecessor index. Brodal bounds worst-case repair after the operation’s node has been supplied. The latter is especially relevant to strict deadlines, but its shared mutable controller is not an append-only old-top implementation. This is a comparison of imported mechanisms and a failed direct transfer, not a native impossibility theorem.

The next decisive test remains a paid current-version selector for late contraction receipts, or an aggregate that avoids destination-bucket insertion. Neither a static prepared pointer nor a semantic quotient supplies that operation. Assessment 244 retains its service-admissible positive control and descending-contraction failure for literal late insertion.

Primary sources and editions actually read

• Paul F. Dietz, Fully Persistent Arrays (Extended Abstract), University of Rochester Technical Report 290, June 1989. Read the complete argument, printed pages 1–8, in the nine-page primary PDF. Repository record. SHA-256: ba157376c0c25e736f8c642b4845ae130d0244a327add15fa10f76f073cdc181.
• Gerth Stølting Brodal, Partially Persistent Data Structures of Bounded Degree with Constant Update Time, BRICS RS-94-35, November 1994, internal title date 8 November. Read all sections and proofs, printed pages 1–24, in the 27-page official BRICS PDF. SHA-256: 5184df0f930affbf63a2960ef94a1c7533aa44547dbac438c7340a93e19db2be. The later journal edition exists, but the proof details below refer to this report.

These are additional primary methods, not replacements for entry 129. Primary PDFs and extracted text remain outside public source. The following exposition records the mechanisms examined and our transfer assessment, without copying the papers.

Dietz: version selection is a predecessor problem

The model supports access at an index of any retained array version and a store creating a child of a chosen version. The version tree is therefore genuinely branching. It is not just a chronological list of updates. Numeric indices lie in a range bounded by the operation count. Array values are inherited from the most recent ancestor that wrote the selected index.

The proof traverses each version twice, on entry and exit. For a fixed index, deleting the version-tree edges at writes partitions inherited values into connected regions; the traversal turns these into contiguous runs. With $m$ writes at that index there are at most $2m+1$ runs. An access becomes predecessor selection among run starts in traversal order. This explains how historical branching becomes an ordered lookup rather than a scan through ancestors. A balanced tree already gives logarithmic access in the number of relevant writes.

The stronger bound requires more than replacing that tree with a fast integer predecessor structure. Two-level order labels represent traversal order; relabeling a block changes many implicit labels. Updating a predecessor structure for every changed label would lose the desired bound. Dietz groups each index’s run starts into buckets of order $\log^2 n$ elements. A balanced tree inside each bucket costs $O(\log\log n)$, while only bucket headers enter the fast predecessor structure. But headers can cluster in the same order-maintenance block, so an average header count is insufficient.

The weighted list-maintenance step addresses that concentration. Each order-maintenance block carries weight $1+\sum_r h(r)\log\log n$ over its records, charging the headers that relabeling that block would affect. Blocks are split by weight, not just by record count. The reduction surrounds a weighted item with dummy items so contiguous relabeling pays the repair weight. A header created by a bucket split incurs extra maintenance, but there are only $O(n/\log^2 n)$ such splits. Thus the bookkeeping is charged to actual updates rather than an assumed even distribution of headers.

The resulting array has linear space, $O(\log\log n)$ access, and amortized expected $O(\log\log n)$ store under the stated integer and hashing machinery. The report also explains why one cannot blindly carry an ephemeral amortized analysis into full persistence: branching can repeat an expensive operation from an old state.

Application assessment. This provides an actual version-aware selector, but its growing integer labels, numeric index access, predecessor operations and randomized storage machinery are not finite-label native primitives. Its bound grows with $n$, and amortized expected update time does not meet a fixed per-symbol deadline. A transfer would need to build and route the index and version encodings from ordinary names, charge relabeling and every old-storage observation, and replace mutable updates with the specified persistent local semantics. The report’s full persistence is a useful semantic control, not a constant-time native compiler.

For finite checking, all default initial runs share a sentinel. That sentinel is treated separately from the statement that a noninitial traversal position begins runs for at most two indices. Counting the common initial position once per index would invalidate that incidence test without changing the run decomposition.

Brodal: worst-case repair uses a shared mutable controller

The base pointer machine has bounded in-degree $b$, bounded out-degree $d$, fixed-size nodes and entry pointers. Historical versions can be queried; only the newest version is updated. Node copying turns an overflowing modification record into a new node and redirects predecessor references. Cascading redirections are represented by a pebble game: an input move adds a pebble at a known node, or replaces an outgoing edge and adds a pebble there; a repair zeros a node and adds pebbles to its predecessors.

The efficient strategy colors edges so each vertex has at most one incoming white edge and there are no white cycles. White components are rooted trees. Each node keeps a round-robin queue of predecessors. A component break blacks its nodes and edges, attaches its old root through the next queued predecessor where possible, and zeros that root. Edge replacement breaks the component before removing a white edge and after replacing a black edge, so it never requires an arbitrary white-component split.

The crucial implementation is indirect color storage. Every white member points to one component record containing its color and root. Changing that shared record blacks a whole component in constant time, regardless of its size. This is a real pointer-machine implementation; its cost is not obtained by silently scanning all members.

The proof bounds how many successor zeroings can occur between two zeroings of a fixed vertex. There is at most one intermediate color-change event, giving two intervals with fixed successors. Round-robin predecessor queues force a blocking white edge after at most $b$ zeroings of a successor. Two intervals initially give $2bd+2$ pebbles; when the middle event contributes two, it removes a later opportunity, tightening the bound to $2bd+1$. A complete bipartite successor example matches that threshold for this strategy.

The report carefully distinguishes implementability from a sharper game bound. Section 6 obtains $d_v+2b_v$, or $d_v+b_v$ in a static graph, using queues with a zero sentinel. Finding the node to zero can require an unbounded predecessor walk, so this strategy is explicitly not efficiently implementable. Section 7 combines sentinels with component records and obtains the implemented locally adaptive bound $2b_vd_v+2b_v-1$. Section 8’s convergent-tree, star and clique adversaries concern the pebble game’s thresholds. They are not native language lower bounds. Section 9 allows undoing the latest update with a modification stack, not arbitrary confluent merges.

Application assessment. Worst-case constant overhead applies per already-addressed pointer-machine step. The strategy is told where the input move occurred. Partial persistence itself can fit chronological whole-store updates; rejecting the method simply because it is not fully persistent would miss the actual issue. The unpaid operations are ordinary-name location, current-version selection, number/version representation and the native realization of mutable controller records.

In particular, the auxiliary component record can have unbounded fan-in even when the base graph has bounded degrees. Applying the same bounded-in-degree theorem recursively to that auxiliary controller is unjustified. Copying the record preserves old aliases but does not route current member reads to the new record. The paper’s repair for unbounded base in-degree uses convergent balanced trees and charges logarithmic access in that degree. None of these observations rules out a different native representation. The useful imported lesson is that repair bursts can be deamortized after the location contract is available.

Independent finite evidence and exact limits

An independent reviewer read the full Brodal argument, checked the native transfer and supplied the standalone semantic checker. Fresh execution passed 90 version-tree snapshots, 116,298 ancestor-versus-run-predecessor reads, 11,024 intervals, 8,060 noninitial boundaries with maximum incidence two, and 83,265 retained-branch value checks. The deterministic cases include chains, stars and branching trees, several index ranges, repeated values and both sibling insertion directions.

A separate 17-index control isolates the common initial sentinel. A shared-record illustration shows that mutating one component record changes all raw aliases, while copying only that record leaves existing aliases pointing to the old value. This illustrates the transfer obligation; it does not simulate Brodal’s pebble game or refute his persistent implementation. The run decomposition is rebuilt using Python lists and ancestor walks as independent oracles. No timing, hash-table complexity, weighted relabeling or native deadline claim follows from these finite checks.

Editorial review and publication scope

Reviewed the recent assessment 240–244 readings, linked learned-filler, deferred-index, multiscale-index and cross-scale-frontier notes, current checkpoint and code-reader navigation. The construction 85 example incorrectly attributed installing the 33-bit receipt to the later 35-bit record. The intervening 513-bit record already services it. The corrected paragraph states that sequence and explains that the 35-bit record leaves the 513-bit receipt pending. The theorem and algorithm are unchanged.

Selected raw formula strings in the multiscale and cross-scale notes now use KaTeX, including the exceptional learned map, logarithmic class index, contraction inequalities and late-class witness parameters. Recent preserved checkpoint targets are labeled with their historical assessment, and missing spaces in those continuation paragraphs are repaired. The active next target is unchanged.

The maintained Python sources retain their exact bytes; the new audit has a highlighted HTML reader, line anchors and an explicit exact raw download. Generated projections, not duplicate hand-edited sources, supply these readings. Scoped structural, link, source-byte and rendered HTML/KaTeX checks accompany the build. The supported viewport browser is unavailable, so this pass does not claim visual clipping or responsive-layout verification. Exact check counts and GitLab-to-Site deployment parity are recorded in integration state. The prior full-suite baseline remains recorded there; this localized review/editorial change uses scoped checks under the root operating contract.

Integration and next decisive test

Source custody is GitLab with pinned primary URLs and hashes. Root CLAIMS.yaml, construction 85, the SAT/scaffold frontier and previous replay, affine, causal and unary controls remain unchanged. Proof evidence here is an imported-method comparison; computation is a finite semantic audit. The failure ledger retains the direct-transfer gaps above and assessment 244’s restricted insertion obstruction. Reopening either route requires an explicit charged selector or append-only controller, not another semantic persistence argument. Reader synthesis is this review and the program checkpoint; the Site publishes their generated readings. Homepage recency and publication ranking are unchanged because no new mathematical result is claimed.

Construct a paid current-version selector for late contraction receipts, or a shared aggregate that bypasses bucket insertion. Ordinary preparation and activation must make the selected shorter answer accessible by its deadline, without supplied routes, stale handles or final traversal. Test both service-admissible sequences and descending contractions. Preserve arbitrary whole-suffix permutations, arbitrary-name routing, cyclic sharing and heterogeneous service as open.

Scheduled completion 150 counts both duties once. Mathematical 148, native 85, window 2 and last reassessment 146 are unchanged. Next is research at 151; dedicated primary review at 155 and editorial at 156. Installed reverse-writer retirement remains separate and unverified.