pith. sign in

arxiv: 2606.05467 · v1 · pith:QWOM6HM4new · submitted 2026-06-03 · 💻 cs.DS

The Cascade Log: Reference-Stable Windowing over Tiered Append Sequences

Faruk Alpay , Levent Sarioglu This is my paper

Pith reviewed 2026-06-28 03:11 UTC · model grok-4.3

classification 💻 cs.DS
keywords tiered append sequencesreference stabilitycoalescing interval mapfragmentationcross-tier anomaliesversioned data structuresappend logsnapshot tokens
0
0 comments X

The pith

The Cascade Log maintains a single coalescing interval map over handles as the sole authority on live versions in tiered append sequences.

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

The paper introduces the Cascade Log to solve reference instability when long append sequences are tiered into a hot stratum and folded cold summaries. It keeps one persistent coalescing interval map that tracks every live handle and merges contiguous same-digest runs into single interval nodes backed by digests. Immutable roots serve as snapshot tokens. The structure eliminates four defined cross-tier anomalies while its space and time costs are expressed solely in terms of fragmentation A, the count of live handles plus maximal same-digest runs. This yields sublinear behavior on append-dominated histories and linear growth only when edits fragment the sequence.

Core claim

The Cascade Log keeps a single persistent coalescing interval map over handles as the sole authority on each live version; folding a contiguous run replaces many singleton entries by one digest-backed interval node, and immutable roots provide snapshot tokens. Its cost is characterized by the fragmentation A, the number of index pieces, namely live handles plus maximal same-digest runs. The index uses Θ(A) space, resolves a point in O(log A), reports a k-handle range in O(log A+k), and performs a appends and s supersedes in O((a/B+s)log A) update work for fold block size B. Matching lower bounds show that Ω(A) space and Ω(log A+k) ordered range cost are unavoidable, and an adversary can forc

What carries the argument

A single persistent coalescing interval map over handles that serves as the sole authority on live versions, folding contiguous runs into digest-backed interval nodes while immutable roots act as snapshot tokens.

If this is right

  • Space usage remains Θ(A) where A counts live handles plus maximal same-digest runs.
  • Point resolution costs O(log A) and ordered k-handle range reporting costs O(log A + k).
  • a appends and s supersedes together cost O((a/B + s) log A) for fold block size B.
  • Matching lower bounds establish that Ω(A) space and Ω(log A + k) range cost are required in the worst case.
  • An adversary can force A = Θ(s), so cost grows linearly only under fragmenting supersedes.

Where Pith is reading between the lines

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

  • The same map could supply stable iterators for other tiered structures such as LSM trees or versioned key-value stores.
  • Tracking A at runtime would give an online signal for when to perform folds or compaction.
  • Immutable roots could be extended to support multi-version concurrency control without extra coordination.

Load-bearing premise

The coalescing interval map eliminates all four cross-tier anomalies and the fragmentation count A captures every operational cost without hidden overheads from the tiering process.

What would settle it

An execution in which a handle minted on hot data returns a dangling, stale, corrupt, or snapshot-skewed result after a fold, or where observed space or update cost exceeds the stated Θ(A) and O((a/B+s)log A) bounds by more than a constant factor.

Figures

Figures reproduced from arXiv: 2606.05467 by Faruk Alpay, Levent Sarioglu.

Figure 1
Figure 1. Figure 1: The Cascade Log. Appends enter the hot stratum 𝑇0; aged blocks fold into digests in colder strata. The versioned interval map spans the working set and the digests and resolves every handle to its live version—a materialised hot record (solid) or a digest reached by stabbing its summarised interval node (dashed). Immutable roots of the map serve snapshot-consistent windows. “Resolve against any past instan… view at source ↗
Figure 2
Figure 2. Figure 2: Reference integrity as the hot capacity tightens (capacity decreases to the right). Left: anomaly rate under the mixed access stream. Right: fraction of the whole history that still resolves (log scale). Flat and the Cascade Log coincide at zero anomalies and full addressability; the tiered baselines degrade. the Cascade Log’s coalesced index is 4.3× smaller and its folds do 6× fewer index writes, with ord… view at source ↗
Figure 3
Figure 3. Figure 3: Left: materialised footprint versus history length (log–log); the Cascade Log working set (dashed) is bounded, and its total stays below HashSpine and far below Flat. Right: retained-mode index size against the number of retained snapshot tokens (Theorem 4.7). constant factor below the Cascade Log, the price it pays for the ordered, snapshot-consistent access a hash cannot give. Append is a single logarith… view at source ↗
Figure 4
Figure 4. Figure 4: Left: index splices per folded record versus block size 𝐵. Append-only folding (edit rate 0) lies on 1/𝐵—one splice per block—so its per-record index work vanishes with 𝐵; edits add a flat, rate-proportional fragmentation charge. Right: index nodes versus 𝑛; the Cascade Log coalesces folded runs to an 𝑜(𝑛) index, while the hash spine keeps 𝑛 entries. 10 4 10 5 records appended, n 10 3 10 4 10 5 index nodes… view at source ↗
Figure 5
Figure 5. Figure 5: Left: index nodes versus 𝑛 for the Cascade Log and PersistentMap (an ordered, persistent map without coalescing); coalescing alone accounts for the gap. Right: ordered-range latency versus the number of handles reported 𝑘; the Cascade Log scales as 𝑘 while the order-less HashSpine pays a full scan. windows can be read against; the snapshot consistency of Theorem 4.2 follows from persistence rather than fro… view at source ↗
Figure 6
Figure 6. Figure 6: Robustness over five seeds per point (95% confidence intervals). Left: anomaly rate versus edit rate; the Cascade Log stays at zero. Right: the Cascade Log index as a fraction of 𝑛 rises with the edit rate (append-only floor 1/𝐵 dotted), so the 𝑜(𝑛) index is an append-dominance property, not a universal one. paper does not attempt. Multiversion and temporal indexing. Serving a read as of a past instant is … view at source ↗
Figure 7
Figure 7. Figure 7: Adversarial fragmentation (Theorem 4.10). Left: index nodes 𝐴 versus the number of evenly spaced (and randomly placed) edits 𝑠; the Cascade Log grows as Θ(𝑠) and never exceeds PersistentMap’s 𝑛. Right: resolution latency versus 𝐴, tracking log2 𝐴, so queries stay logarithmic even at worst-case fragmentation. 8 Conclusion A tiered append sequence keeps its working set bounded, but the obvious way to do so d… view at source ↗
Figure 8
Figure 8. Figure 8: Left: resolution latency versus history length to 𝑛 = 106 (log 𝑥); HashSpine is a constant factor below the Cascade Log, the tiered baselines faster still but unable to read the past or, for NaiveTier, correctly. Right: vii height against a 2 log2 𝑛 guide—logarithmic with a small constant. 0.2 0.4 0.6 0.8 budget (fraction of candidate cost) 0.7 0.8 0.9 1.0 relevance coverage (normalised) optimal partial en… view at source ↗
Figure 9
Figure 9. Figure 9: Budgeted windows. Left pair: relevance coverage and worst-case approximation ratio of prefix-by-rank, the simple greedy ( 1 2 (1−1/𝑒)), the partial enumeration (1−1/𝑒), and the optimum. Right: on the family of Proposition 4.14, prefix-by-rank is a Θ(1/𝑘) fraction of the optimum while both greedies are optimal (log–log). implementation is a single-threaded reference in a managed language, so absolute latenc… view at source ↗
read the original abstract

A long-running append-mostly sequence, such as an edit log, event store, or versioned working set, is usually tiered into a bounded hot stratum and colder folded summaries. This saves memory but breaks stable references: a handle minted while a record is hot may later be resolved after the record has moved into a digest, after it has been superseded, or while a fold is in flight. We define the resulting cross-tier anomalies--dangling, stale, corrupt, and snapshot-skewed resolution--and present the Cascade Log, a reference-stable tiered append structure. The structure keeps a single persistent coalescing interval map over handles as the sole authority on each live version; folding a contiguous run replaces many singleton entries by one digest-backed interval node, and immutable roots provide snapshot tokens. Its cost is characterized by the fragmentation $A$, the number of index pieces, namely live handles plus maximal same-digest runs. The index uses $\Theta(A)$ space, resolves a point in $O(\log A)$, reports a $k$-handle range in $O(\log A+k)$, and performs $a$ appends and $s$ supersedes in $O((a/B+s)\log A)$ update work for fold block size $B$. Matching lower bounds show that $\Omega(A)$ space and $\Omega(\log A+k)$ ordered range cost are unavoidable, and an adversary can force $A=\Theta(s)$. Thus the index is sublinear on append-dominated histories and grows linearly only under fragmenting edits. A reference implementation and reproducible experiments to $10^6$ records validate the anomaly-freedom and the fragmentation bounds.

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

0 major / 2 minor

Summary. The paper presents the Cascade Log, a reference-stable tiered append structure for long-running append-mostly sequences such as edit logs and event stores. It defines four cross-tier anomalies (dangling, stale, corrupt, and snapshot-skewed resolution) and claims that a single persistent coalescing interval map over handles serves as the sole authority on each live version. Folding a contiguous run replaces many singleton entries with one digest-backed interval node, while immutable roots provide snapshot tokens. Costs are characterized by the fragmentation measure A (live handles plus maximal same-digest runs): the index uses Θ(A) space, resolves a point in O(log A), reports a k-handle range in O(log A + k), and performs a appends and s supersedes in O((a/B + s) log A) for fold block size B. Matching lower bounds establish that Ω(A) space and Ω(log A + k) ordered range cost are unavoidable, with an adversary forcing A = Θ(s). A reference implementation and reproducible experiments to 10^6 records are provided to validate anomaly-freedom and the fragmentation bounds.

Significance. If the claims hold, the result is significant for data structures supporting versioned and append-dominated workloads, as it achieves reference stability across hot/cold tiers while remaining sublinear in space and query cost on append-heavy histories and only linear under fragmenting edits. The explicit matching lower bounds and the direct validation via reference implementation plus experiments to 10^6 records are strengths that ground the anomaly-freedom and A-based cost claims. The structural definition of A as live handles plus maximal same-digest runs, together with the adversary argument for tightness, avoids circularity and provides a clean characterization.

minor comments (2)
  1. [Abstract] Abstract: the fold block size B appears in the update complexity bound without a preceding definition or parenthetical; a brief inline clarification would improve readability for readers encountering the bound for the first time.
  2. The manuscript would benefit from an illustrative figure or small example showing the coalescing interval map state before and after a fold operation, to make the replacement of singleton entries by digest-backed interval nodes concrete.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the detailed and positive summary of our work on the Cascade Log. The recommendation for minor revision is appreciated, and we note that the report contains no enumerated major comments requiring point-by-point rebuttal.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper defines fragmentation A directly as the count of live handles plus maximal same-digest runs in its coalescing interval map, then states that the index occupies Θ(A) space and supports the listed query/update bounds in terms of A. Matching lower bounds are presented as information-theoretic necessities on any structure that must track the same live versions and digest runs, with an adversary argument showing A=Θ(s) under supersedes; these are not reductions to fitted parameters or self-referential equations. The central claims rest on the explicit construction, the anomaly definitions, and external validation via reference implementation plus experiments to 10^6 records rather than on self-citation chains or ansatzes imported from prior author work. No load-bearing step equates a derived quantity to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the domain model of tiered append sequences and the correctness of the interval map in eliminating anomalies; no free parameters are introduced, and the invented entity is the structure itself.

axioms (1)
  • domain assumption Append-mostly sequences can be tiered into a bounded hot stratum and colder folded summaries while still requiring stable reference resolution across tiers.
    This premise underlies the definition of cross-tier anomalies and the need for the Cascade Log.
invented entities (1)
  • coalescing interval map no independent evidence
    purpose: Sole persistent authority on each live version that coalesces runs during folding
    New data structure component introduced to solve the reference stability problem.

pith-pipeline@v0.9.1-grok · 5832 in / 1567 out tokens · 69904 ms · 2026-06-28T03:11:15.215358+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

28 extracted references · 25 canonical work pages

  1. [1]

    The input/output complexity of sorting and related problems.Communi- cations of the ACM, 31(9):1116–1127, 1988

    Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems.Communi- cations of the ACM, 31(9):1116–1127, 1988. doi: 10.1145/48529.48535

    work page doi:10.1145/48529.48535 1988

  2. [2]

    McCreight

    RudolfBayerandEdwardM.McCreight. Organizationandmaintenanceoflargeorderedindexes.ActaInformatica, 1(3):173–189, 1972. doi: 10.1007/BF00288683

    work page doi:10.1007/bf00288683 1972

  3. [3]

    Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem and related problems.Journal of Computer and System Sciences, 65(1):38–72, 2002. doi: 10.1006/jcss.2002.1822

    work page doi:10.1006/jcss.2002.1822 2002

  4. [4]

    An asymptotically optimal multiversion B-tree.The VLDB Journal, 5(4):264–275, 1996

    Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, and Peter Widmayer. An asymptotically optimal multiversion B-tree.The VLDB Journal, 5(4):264–275, 1996. doi: 10.1007/s007780050028. 20 Table 3:Result files and the artifacts they produce. File (anc/results/) Artifact headline.csvTable 1 anomaly_vs_capacity.csvFigure 2 scaling.csvFigure 3, Figu...

    work page doi:10.1007/s007780050028 1996

  5. [5]

    Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. Journal of Algorithms, 1(4):301–358, 1980. doi: 10.1016/0196-6774(80)90015-2

    work page doi:10.1016/0196-6774(80)90015-2 1980

  6. [6]

    Bernstein and Nathan Goodman

    Philip A. Bernstein and Nathan Goodman. Multiversion concurrency control—theory and algorithms.ACM Transactions on Database Systems, 8(4):465–483, 1983. doi: 10.1145/319996.319998

    work page doi:10.1145/319996.319998 1983

  7. [7]

    Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors.Communications of the ACM, 13 (7):422–426, 1970. doi: 10.1145/362686.362692

    work page doi:10.1145/362686.362692 1970

  8. [8]

    Boehm, Russ Atkinson, and Michael Plass

    Hans-J. Boehm, Russ Atkinson, and Michael Plass. Ropes: An alternative to strings.Software: Practice and Experience, 25(12):1315–1330, 1995. doi: 10.1002/spe.4380251203

    work page doi:10.1002/spe.4380251203 1995

  9. [9]

    The anatomy of a large-scale hypertextual Web search engine.Computer Networks and ISDN Systems, 30(1–7):107–117, 1998

    Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual Web search engine.Computer Networks and ISDN Systems, 30(1–7):107–117, 1998. doi: 10.1016/S0169-7552(98)00110-X

    work page doi:10.1016/s0169-7552(98)00110-x 1998

  10. [10]

    Lower bounds for external memory dictionaries

    Gerth Stølting Brodal and Rolf Fagerberg. Lower bounds for external memory dictionaries. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 546–554, 2003

    2003

  11. [11]

    Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. a data structuring technique.Algorithmica, 1 (2):133–162, 1986. doi: 10.1007/BF01840440

    work page doi:10.1007/bf01840440 1986

  12. [12]

    The ubiquitous B-tree.ACM Computing Surveys, 11(2):121–137, 1979

    Douglas Comer. The ubiquitous B-tree.ACM Computing Surveys, 11(2):121–137, 1979. doi: 10.1145/356770. 356776

    work page doi:10.1145/356770 1979

  13. [13]

    Makingdatastructurespersistent.Journal of Computer and System Sciences, 38(1):86–124, 1989

    JamesR.Driscoll,NeilSarnak,DanielD.Sleator,andRobertE.Tarjan. Makingdatastructurespersistent.Journal of Computer and System Sciences, 38(1):86–124, 1989. doi: 10.1016/0022-0000(89)90034-2

    work page doi:10.1016/0022-0000(89)90034-2 1989

  14. [14]

    Haveliwala

    Taher H. Haveliwala. Topic-sensitive PageRank: A context-sensitive ranking algorithm for Web search.IEEE Transactions on Knowledge and Data Engineering, 15(4):784–796, 2003. doi: 10.1109/TKDE.2003.1208999

    work page doi:10.1109/tkde.2003.1208999 2003

  15. [15]

    Linearizability: a correctness condition for concurrent objects,

    Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects.ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990. doi: 10.1145/78969.78972

    work page doi:10.1145/78969.78972 1990

  16. [16]

    The budgeted maximum coverage problem.Information Processing Letters, 70(1):39–45, 1999

    Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. The budgeted maximum coverage problem.Information Processing Letters, 70(1):39–45, 1999. doi: 10.1016/S0020-0190(99)00031-9

    work page doi:10.1016/s0020-0190(99)00031-9 1999

  17. [17]

    Eugene W. Myers. An O(ND) difference algorithm and its variations.Algorithmica, 1(1–4):251–266, 1986. doi: 10.1007/BF01840446

    work page doi:10.1007/bf01840446 1986

  18. [18]

    Ananalysisofapproximationsformaximizing submodular set functions—I.Mathematical Programming, 14(1):265–294, 1978

    GeorgeL.Nemhauser,LaurenceA.Wolsey,andMarshallL.Fisher. Ananalysisofapproximationsformaximizing submodular set functions—I.Mathematical Programming, 14(1):265–294, 1978. doi: 10.1007/BF01588971. 21

    work page doi:10.1007/bf01588971 1978

  19. [19]

    The log-structured merge-tree (LSM-tree)

    Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4):351–385, 1996. doi: 10.1007/s002360050048

    work page doi:10.1007/s002360050048 1996

  20. [20]

    Skip lists: A probabilistic alternative to balanced trees.Communications of the ACM, 33(6): 668–676, 1990

    William Pugh. Skip lists: A probabilistic alternative to balanced trees.Communications of the ACM, 33(6): 668–676, 1990. doi: 10.1145/78973.78977

    work page doi:10.1145/78973.78977 1990

  21. [21]

    Time-space trade-offs for predecessor search

    Mihai Pˇatraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. InProceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 232–240, 2006. doi: 10.1145/ 1132516.1132551

    arXiv 2006

  22. [22]

    Betty Salzberg and Vassilis J. Tsotras. Comparison of access methods for time-evolving data.ACM Computing Surveys, 31(2):158–221, 1999. doi: 10.1145/319806.319816

    work page doi:10.1145/319806.319816 1999

  23. [23]

    Neil Sarnak and Robert E. Tarjan. Planar point location using persistent search trees.Communications of the ACM, 29(7):669–679, 1986. doi: 10.1145/6138.6151

    work page doi:10.1145/6138.6151 1986

  24. [24]

    Raimund Seidel and Cecilia R. Aragon. Randomized search trees.Algorithmica, 16(4–5):464–497, 1996. doi: 10.1007/BF01940876

    work page doi:10.1007/bf01940876 1996

  25. [25]

    Sleator and Robert E

    Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules.Communications of the ACM, 28(2):202–208, 1985. doi: 10.1145/2786.2793

    work page doi:10.1145/2786.2793 1985

  26. [26]

    Sleator and Robert E

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

  27. [27]

    doi: 10.1145/3828.3835

    work page doi:10.1145/3828.3835

  28. [28]

    Robert E. Tarjan. Amortized computational complexity.SIAM Journal on Algebraic and Discrete Methods, 6(2): 306–318, 1985. doi: 10.1137/0606031. 22

    work page doi:10.1137/0606031 1985