Service-Cut Certificates for Aligned Eviction in Tiered Cache Networks
arXiv:2606.22270v1 [cs.DS] 20 Jun 2026
Faruk Alpay∗
Levent Sarıoğlu
Department of Computer Engineering, Bahçeşehir University Istanbul, Turkey [email protected], [email protected]
Abstract In a tiered cache, eviction is a graph decision: removing one aligned storage block can disconnect downstream demand that never addressed that block directly, so request recency alone cannot price the action. This paper studies aligned eviction as a vertex-separation problem and gives a selection rule whose decisions carry independently checkable service-cut evidence. For every candidate block, it computes the exact weighted downstream demand cut, rejects actions that disconnect protected demand, and selects the minimum-impact admissible eviction. Reclamation is characterized as vertex separation: minimum-location reclamation reduces to node-capacitated flow, while minimum aligned block actions are NP-complete. In two-hop cache networks, one streaming pass evaluates every candidate impact; a matching adversarial construction proves that a history-only victim selector has unbounded one-step damage. The packet-scale implementation combines a seed-indexed exact-cardinality residency structure with collision-aware, 32-bank impact counters. Replay compression makes the result auditable: counter intervals reproduce the stream, exact monoid summaries retain every reported additive statistic, and a counting lower bound quantifies the state required by any exact all-candidate summary. A 144-scenario evaluation processes 582.90 trillion packets (404.86 PiB of simulated payload), validates the coordinate expectations, and exposes a zero-impact extreme-value transition near N ζ = log m. Complete impact vectors, decoded audit samples, telemetry, and logs remain within the ancillary-file budget. Finally, invalidation is monotone replicated state: fair asynchronous delivery converges without coordination, with a diameter bound under synchronous full-edge rounds. The architecture therefore binds capacity reclamation, path continuity, and distributed invalidation to one certifying interface.
1
Introduction
A tiered cache network couples storage placement to service reachability. An origin retains the authoritative copy, intermediate locations hold resident replicas, and directed transfer links determine which replicas can serve downstream demand. The near tier is capacity-limited, but its eviction unit is a fixed-size aligned block rather than an isolated object. Reclaiming one block may therefore remove an intermediate service cut and disconnect demand far from the physical storage action. An eviction layer that observes only request recency cannot state, let alone certify, this graph-level consequence. Request recency alone does not measure this damage. A block that has not been requested recently may be the only resident parent of a large demand set. Conversely, a frequently accessed ∗
Corresponding author: [email protected].
1
block may be redundant because the same demand has several resident parents. The eviction problem therefore has two parts: identify the graph cut induced by a candidate block, and expose enough evidence that another implementation can check the decision. The design objective is a certifying interface: before mutating residency, expose the exact downstream service loss, prove that protected demand remains connected, and make the resulting invalidation converge across replicas without global coordination. The construction draws on caching networks [1, 2], vertex connectivity [3, 4], online paging [7, 8], certifying algorithms [6], and monotone replicated state [10, 12, 13]. Contributions. 1. A shared reachability certificate represents the exact pre- and post-eviction service sets. It avoids one certificate per disconnected endpoint, has linear size, and verifies in linear time for one candidate (Lemma 6.1). 2. Reclamation is characterized as vertex separation. Minimum-location reclamation is a nodecapacitated flow problem, minimum aligned block actions are NP-complete, and alignment yields an exact reclaimable-capacity threshold (Theorems 5.1, 5.2, and 3.4). 3. A one-pass accumulator evaluates all candidate blocks simultaneously in two-hop cache networks (Theorem 7.1). A topology-oblivious selector can have an arbitrarily large one-step damage ratio, whereas minimum impact is optimal for the current state (Theorems 6.8 and 6.7). 4. A constant-state affine index enforces exact resident cardinality in both demand strata. Warp grouping preserves exact impact vectors but has only collision-dependent savings, quantified by Corollary 7.3; sharded counter banks remove address conflicts and yield the measured crossover gain (Theorem 7.5 and Propositions 7.2–7.4). Replay compression then makes the packet experiment compatible with a small research artifact: a seed and counter interval reproduce the stream, and an exact monoid summary preserves every reported additive metric (Theorems 7.10 and 7.11). The artifact retains full candidate vectors, decoded samples, telemetry, logs, and independent validation. The distributed invalidation result is stated with the scheduling assumptions made explicit: fair asynchronous delivery gives eventual convergence, while a diameter bound requires synchronous full-edge rounds. Recoverable and irreversible eviction are handled by separate state transitions rather than conflated with cache replacement.
2
Transfer networks and aligned eviction
Definition 2.1 (Transfer network). A transfer network is a tuple N = (V, E, Π, ρ) where V is a finite nonempty set of locations, E ⊆ V × V is a transfer relation (u → v means a resident copy at u may populate or serve v), and ρ ∈ V is the non-evictable origin. Put C = V \ {ρ}. The alignment Π is a partition of the cacheable locations C into blocks of size β. For v ∈ C, let B(v) ∈ Π be its block. A residency is the set R ⊆ V of locations holding a resident copy, with ρ ∈ R always. A location is served when a resident copy reaches it from the origin over resident locations. Writing G↾X for the subgraph of (V, E) induced by X, Reach(ρ, X) = {v ∈ X : there is an E-path from ρ to v all of whose nodes lie in X}, 2
with Reach(ρ, X) = ∅ when ρ ∈ / X; the served set under R is Reach(ρ, R). An eviction drops residency at an aligned S ⊆ C, leaving served set Reach(ρ, R \ S). S Definition 2.2 (Block closure, aligned set). For X ⊆ C put ⌈X⌉ = {B ∈ Π : B ∩ X ̸= ∅}, the smallest union of blocks containing X. A set S ⊆ C is aligned if S = ⌈S⌉. Proposition 2.3 (Block closure is a closure operator). The map ⌈·⌉ is extensive, monotone and idempotent, and the aligned subsets of C form a complete lattice closed under arbitrary unions and intersections. Proof. Extensivity and monotonicity are immediate; idempotence holds because a block meeting ⌈X⌉ already meets X. A subset is aligned exactly when it is a union of blocks, and unions and intersections of unions of blocks are unions of blocks, giving a complete sublattice of (2C , ⊆). Let T ⊆ C be the target region to reclaim and put P = C \ T . Bounded near tier and protection. A subset F ⊆ C is the near tier, holding at most κ resident copies, and a subset of cacheable locations is protected, hence exempt from eviction. These explain why reclamation is undertaken, namely to keep |R ∩ F | ≤ κ, and which evictions are admissible, but they do not enter the basic separation equivalence.
3
Aligned reclamation, collapse, and granularity
The direct model has no intermediaries, so a location is served exactly when resident. Section 4 restores routing. Definition 3.1 (Reclamation, direct model). In the direct model an eviction S ⊆ C reclaims T if T ⊆ S, and is aligned if S = ⌈S⌉. Theorem 3.2 (Reclamation lattice). The aligned reclamations of T are exactly the aligned supersets of T . They are closed under intersection and form a principal filter in the lattice of aligned sets with least element ⌈T ⌉. Hence ⌈T ⌉ is the unique minimum aligned reclamation, and its over-eviction is ⌈T ⌉ \ T = {v ∈ / T : B(v) ∩ T ̸= ∅}, the content sharing a block with the target region. Proof. A set is an aligned reclamation iff it is aligned and contains T . If S is such, then ⌈T ⌉ ⊆ ⌈S⌉ = S by monotonicity and idempotence; conversely ⌈T ⌉ is aligned and contains T , hence an aligned reclamation. The collection is {S : ⌈T ⌉ ⊆ S = ⌈S⌉}, a principal filter with least element ⌈T ⌉, closed under intersection by Proposition 2.3. The over-eviction is ⌈T ⌉ \ T . Theorem 3.3 (Fragmentation collapse). In the direct model, every aligned reclamation of T equals C iff ⌈T ⌉ = C iff every block meets T ; when this holds the over-eviction is exactly P . Proof. By Theorem 3.2 the least aligned reclamation is ⌈T ⌉, so all equal C iff ⌈T ⌉ = C, i.e. every block meets T . Then ⌈T ⌉ \ T = C \ T = P . Beyond the all-or-nothing statement, alignment fixes the exact reclaimable capacity. Let N = |Π| be the number of blocks and, for X ⊆ C, write b(X) = |{B ∈ Π : B ∩ X ̸= ∅}| for the number of blocks X touches. Theorem 3.4 (Granularity and reclaimable capacity). Let A ⊆ C be the protected (active) set. (1) The minimum aligned reclamation of T has size β b(T ). 3
(2) At most N −b(A) blocks are evictable, so at most (N −b(A)) β units of capacity are reclaimable. (3) No reclamation is possible, that is the system can free nothing, iff b(A) = N : the active set touches every block. Proof. (1) By Theorem 3.2 the minimum aligned reclamation is ⌈T ⌉, a union of exactly the b(T ) blocks meeting T , of size β b(T ). (2) A block containing a protected location cannot be evicted; there are b(A) such blocks, leaving N −b(A) evictable, hence at most (N −b(A))β reclaimable units. (3) Reclamation frees nothing iff no block is evictable iff every block contains a protected location iff b(A) = N . Theorem 3.4(3) is an exact threshold: as the active footprint spreads to touch every block, reclaimable capacity falls to zero independently of how much nominal capacity remains. The coarser the alignment, the fewer blocks and the sooner b(A) reaches N ; in the limit of a single block any active location forbids all reclamation.
4
Routed reclamation and separation certificates
With intermediaries restored, evicting aligned S ⊆ C leaves served set Reach(ρ, V \ S). A location is reclaimed only when it is no longer reachable from the origin through resident locations. Definition 4.1 (Reclamation, routed model). An aligned eviction S ⊆ C reclaims T if T ∩ Reach(ρ, V \ S) = ∅. Lemma 4.2 (Reclamation is separation). S reclaims T iff S is an (ρ, T )-vertex separator: every E-path from ρ to a location of T contains a node of S. Proof. t ∈ Reach(ρ, V \ S) iff some E-path from ρ to t avoids S; so T ∩ Reach(ρ, V \ S) = ∅ iff no such path exists for any t ∈ T . Write H = G↾(V \ S). Definition 4.3 (Certificates). Fix S ⊆ C and a location t ∈ / S. A residual-service certificate for t is a simple E-path ρ = v0 , . . . , vk = t with all vi ∈ / S. A separation certificate for t is a set C ⊆ V \ S with t ∈ C, ρ ∈ / C, backward closed in H: u → w in H with w ∈ C implies u ∈ C. Theorem 4.4 (Certificate dichotomy). For every location t ∈ / S and every S ⊆ C, exactly one holds: (a) a residual-service certificate for t, simple and of length at most |V | − 1; or (b) a separation certificate for t of size at most |V |. Either certificate is verifiable in O(|V | + |E|) time in an adjacency-list representation (the path case is O(|V |) when edge membership is constant-time). Moreover S reclaims T iff every t ∈ T either lies in S or is in case (b). Proof. Put C ∗ = {w ∈ V \ S : t is reachable from w in H}, which contains t and is backward closed. If ρ does not reach t in H, then ρ ∈ / C ∗ , a separation certificate verified by one edge scan; no residual path exists. If ρ reaches t in H, removing cycles gives a simple residual path; no separation certificate exists, since tracing that path backwards through any backward-closed C ∋ t forces ρ ∈ C. Reachability of t in H is definite, so exactly one case holds. The last claim also accounts for targets directly removed by S and then applies Lemma 4.2 to the remainder. The two families are dual presentations of one boundary in the certifying-algorithm sense [6]: a path exhibits service, a separation set exhibits its impossibility, both checkable independently of how they arose and in linear time. 4
5
Flow–cut duality and the cost of reclamation
Theorem 5.1 (Flow–cut duality). The minimum number of cacheable locations whose eviction reclaims T equals the maximum number of ρ–T paths that are vertex-disjoint outside their common origin (their endpoints in T are therefore distinct), and is computable in polynomial time. Proof. A minimum reclaiming eviction is a minimum (ρ, T )-vertex separator (Lemma 4.2), where targets themselves may be evicted. Split every v ∈ C into an in-node and out-node joined by a unit-capacity arc, give transfer arcs infinite capacity, and join the out-copy of each t ∈ T to a super-sink by an infinite-capacity arc. An integral maximum flow selects paths that share only ρ; unit capacity at target vertices also forces distinct endpoints. Conversely, every such path family requires a distinct evicted vertex. Node-capacitated max-flow, equivalently this form of Menger’s theorem [3, 4], gives the equality and a polynomial algorithm. Theorem 5.2 (Hardness of minimum-action reclamation). Given a protected set A ⊇ T , deciding whether some aligned reclamation S ⊆ C \ A acts on at most k blocks is NP-complete, even when every block has the same size. Proof. Membership follows by guessing the blocks and checking reachability. For hardness reduce from Set Cover [5]. Given universe U , sets Q1 , . . . , Qm , and budget k, assume every element occurs in at least one set. For each element e, make one directed ρ–t chain whose internal vertices are ve,j for the indices j with e ∈ Qj , in any fixed order. Different element chains share only ρ and t. Put all occurrence vertices ve,j with the same set index j into one block. Thus evicting block j cuts exactly the element chains covered by Qj . Let β be the largest block size, pad smaller blocks with isolated dummy locations, and put t in a separate protected block padded to size β. There is an aligned reclamation using at most k unprotected blocks iff the corresponding sets cover every element of U . The construction is polynomial and all blocks have size β. The split is exact: minimising evicted locations is a polynomial cut, while minimising eviction actions is intractable, since one action drops a whole block and minimisation becomes a covering problem. The certificate sizes are also best possible. Theorem 5.3 (Certificate lower bound). There are networks with |V | = n on which every residualservice certificate has length n − 1 and, after a singleton-block eviction, every separation certificate has size at least n − 2. The O(|V |) bounds of Theorem 4.4 are therefore asymptotically tight. Proof. On the directed path ρ → v1 → · · · → vn−1 = t with S = ∅, the only ρ–t path has length n − 1. For the separation side, use ρ → w1 → · · · → wn−1 = t and evict the singleton block {w1 }. In the residual graph, backward closure forces every certificate containing t to contain w2 , . . . , wn−1 , exactly n − 2 vertices.
6
An operational model and certifying online eviction
The operational layer consists of a transition system over residency, an exact witness of downstream demand lost by an eviction, and an online policy for the classical block-reference specialization. Reachability-aware damage is a network quantity; the usual competitive paging bound applies only after projecting requests to independently cacheable blocks.
5
6.1
Operational model
Let D be a finite set of demand endpoints, disjoint from V , and let ED ⊆ V × D contain the final service links. For residency R, define Serve(R) = {d ∈ D : ∃u ∈ Reach(ρ, R) with (u, d) ∈ ED }. Demand endpoints are clients, not cache slots, and therefore need not be resident. This convention removes an ambiguity between a cache location and a requester. The state is a pair σ = (R, µ) with residency R ⊆ V (ρ ∈ R) and a status map µ : C → {res, rec, free} recording whether content is resident, recoverable by reload, or freed. The capacity invariant is |R ∩ F | ≤ κ. The transitions are request(d),
evict(B),
reload(B),
free(B),
invalidate(S),
where B ranges over blocks and d ∈ D. A request is a hit exactly when d ∈ Serve(R); otherwise it is a service fault and the policy may repopulate a service path, evicting blocks as needed to respect capacity. A protected demand set Dp must remain in Serve(R). The implementation maintains capacity, exact service queries, protection, and eventual invalidation closure.
6.2
An exact downstream-cost witness
Give each endpoint a nonnegative weight w(d), such as its observed packet or byte count. The decisive operational quantity is the weighted demand that an eviction disconnects. Lemma 6.1 (Impact oracle). Let R be the residency and B ∈ Π. Define X MissR (B) = Serve(R) \ Serve(R \ B), Iw (B) =
w(d).
d∈MissR (B)
The set MissR (B), its weight, and a shared certificate of both the pre- and post-eviction service sets are computable and verifiable in O(|V | + |E| + |ED |) time and linear space. Proof. Traverse G↾R and G↾(R \ B) to obtain reachable sets R0 , R1 and predecessor forests rooted at ρ. Scan ED to derive Di = {d : ∃u ∈ Ri , (u, d) ∈ ED }, whence MissR (B) = D0 \D1 and the weighted sum follows. A verifier checks each predecessor forest and then scans every resident transfer edge to ensure that no edge leaves Ri for an omitted resident vertex. These two facts certify that Ri is exactly the reachable set, rather than merely a subset. A final scan of ED certifies D0 , D1 . The certificate is shared by all disconnected endpoints; emitting a separate separation set per endpoint could require quadratic output and is neither claimed nor needed. Lemma 6.1 turns eviction into a decision with a verifiable consequence. A block is admissible iff MissR (B) ∩ Dp = ∅, which the same certificate checks.
6.3
Online block-reference specialization
For comparison with classical paging, consider the specialization in which each request names one block, a hit means that block is resident, one block is admitted per fault, and at every eviction an admissible unmarked block exists. The near tier then has k = ⌊κ/β⌋ slots. The policy maintains a mark bit per resident block, set on access and cleared at the end of a phase; on a fault it evicts an admissible unmarked block of least Iw (B). 6
Theorem 6.2 (Competitive guarantee). In the block-reference specialization, marking with impact tie-breaking is k-competitive in service faults: for every request sequence, Alg ≤ k · Opt + k. No deterministic online policy achieves a ratio below k. If p slots are occupied by permanently pinned blocks, the same statement holds with k ′ = k − p for the remaining reference stream. Proof. Partition the sequence into phases, each a maximal run touching at most k distinct blocks. Within a phase marking faults at most once per distinct block, irrespective of which unmarked block the impact tie-breaker selects, hence at most k times. The first request of phase i + 1 and the k distinct blocks of phase i form k + 1 distinct blocks, so any k-slot cache faults at least once across that boundary. With q phases, Opt ≥ q − 1 and Alg ≤ kq, giving the stated inequality. The lower bound is the classical deterministic paging bound [7, 8]. Permanently pinning p blocks leaves an ordinary k ′ -slot instance on the remaining blocks. Remark 6.3 (Non-uniform fetch cost). When a fault has a block-dependent retrieval cost, the specialization becomes weighted caching. The impact certificate is unchanged, but the unweighted marking proof above cannot simply be reused; an appropriate weighted-caching algorithm and bound must be selected for that cost model.
6.4
Maintenance cost
Theorem 6.4 (Static and batched maintenance). For one fixed residency, reachability and a certificate are computed in O(|V | + |E|) time. Under straightforward re-traversal, q candidate-impact queries cost O(q(|V | + |E| + |ED |)). Given one batch of deletions, exact post-batch reachability is recomputed in O(|V | + |E|) time; q sequential states therefore cost O(q(|V | + |E|)) by this method. Because Π is static, storing a block identifier at each location gives B(v) in O(1) time; an alleged eviction set is checked for alignment in time linear in its representation. Proof. The bounds follow from breadth-first or depth-first traversal and Lemma 6.1; applying the same traversal independently to q states multiplies the cost by q. The final claims follow from the explicit static partition map. No stronger decremental bound is inferred merely from the fact that each block is deleted once; cycles make such a claim nontrivial. Remark 6.5 (General regime). Under interleaved eviction and reload the served set is fully dynamic directed reachability. The stated bounds cover re-traversal in a general graph and the one-pass specialization evaluated in Section 7; a stronger dynamic bound would require a separate data structure.
6.5
Why reachability-awareness is necessary
Topology information is necessary for bounded one-step damage. A history-only victim order cannot distinguish two states with the same request metadata but different downstream service relations. Definition 6.6 (Topology-oblivious victim selector). A deterministic victim selector is topologyoblivious if its choice among resident candidate blocks depends on request-history metadata and the block partition but is invariant to E, ED , and the demand weights. LRU, FIFO, LFU, CLOCK, random-with-a-fixed-seed, and an unweighted marking tie-breaker have this property. Theorem 6.7 (Per-step optimality of impact pricing). At any state, evicting an admissible block of minimum Iw (·) leaves the maximum total served demand weight attainable by evicting one admissible block. A selected block has a linear-size certificate; selecting and certifying the minimum among q candidates by general-graph traversal costs O(q(|V | + |E| + |ED |)). 7
Proof. By Lemma 6.1, evicting B removes demand of total weight exactly Iw (B). Subtracting this value from the pre-eviction served weight proves the first claim. Lemma 6.1 supplies a certificate for each candidate evaluation, and Theorem 6.4 gives the stated total cost. Theorem 6.8 (Unbounded one-step damage of topology-obliviousness). For every deterministic topology-oblivious selector, every m ≥ 1, and every state with at least two resident candidate blocks, there is a demand topology consistent with the same history metadata on which its chosen eviction has impact at least m while another candidate has impact 1. Its one-step damage ratio is therefore unbounded. Proof. Fix the residency, partition, and all history metadata. Since the selector ignores topology, it chooses some block B ∗ before ED is specified. Add m unit-weight demand endpoints whose only service links originate in B ∗ . For every other candidate block, add one private unit-weight endpoint and no further demand. All candidates remain resident and all pre-eviction demand is served. Evicting B ∗ disconnects m endpoints, whereas evicting any other candidate disconnects exactly one. The metadata observed by the topology-oblivious selector did not change, so it still chooses B ∗ ; impact pricing chooses a unit-impact block. Letting m grow proves the claim. Remark 6.9. Theorem 6.8 isolates the information gap behind request-history eviction under path replication [1]: a block may carry substantial downstream demand without being recently requested itself. The experiment in Section 7 measures this one-step damage directly.
7
Replay-compressed packet-scale evaluation
The general impact oracle performs one reachability computation per candidate. The implementation evaluates a two-hop specialization ρ → Π → D in one streaming pass, with at most r candidate cache blocks per demand endpoint. A packet contributes one unit of packet weight and its encoded size in byte weight; one packet-impact and one byte-impact counter are kept per block. Theorem 7.1 (One-pass impact accumulation). For a two-hop network, let P (d) ⊆ Π be the distinct parent blocks of demand d, and let zb ∈ {0, 1} indicate whether block b is resident. For any packet stream d1 , . . . , dN with nonnegative integer packet weights ai , N X X I(b) = ai 1b ∈ P (di ), zb = 1, zc = 1 . i=1
c∈P (di )
All values I(b) are computed exactly in one pass using O(|Π|) counters and O(N r) work. Parallel atomic addition preserves the result under any execution order. Proof. A served packet is lost by evicting b exactly when b is its unique resident parent, which is the indicator in the display. During one pass, inspect the at most r distinct parents, identify whether the resident-parent count is one, and if so add ai to that parent’s counter. Every packet contributes to exactly the blocks prescribed by the formula, proving exactness. Integer addition is associative and commutative; atomic updates therefore produce the same counter vector under every interleaving, provided the counters do not overflow. Proposition 7.2 (Warp-aggregated exact updates). In one warp iteration, partition the lanes whose packet has exactly one resident parent by that parent identifier. Replacing every lane’s two global atomic additions by one packet-count addition and one byte-sum addition per nonempty class leaves both impact P vectors unchanged. If the class sizes are g1 , . . . , gh , the number of global impact atomics falls from 2 j gj to 2h. 8
Proof. All lanes in class j target the same block. Their packet contribution is gj and their byte contribution is the class byte sum. Associativity and commutativity of integer addition make one update by each class total identical to the lane-wise updates. The operation count follows directly. Corollary 7.3 (Collision-sparse warp regime). For a warp of W independently generatedPpackets, let αb be the probability that one packet has b as its unique resident parent and put A = b αb . If L is the number of lane-wise impact updates and G the number after grouping by target, then P X W E[L − G] W − 1 b αb2 E[L − G] ≤ αb2 , ≤ . 2 E[L] 2 A b
If maxb αb = O(1/|Π|), the fractional opportunity for warp aggregation is O(W/|Π|). Proof. If nb lanes target b, grouping saves (nb − 1)+ updates, and (nb − 1)+ ≤ n2b . Summing over P 2 targets and taking expectationsPgives E[L − G] ≤ W b αb . Since E[L] = W A, division proves 2 2 the second inequality. Finally, b αb ≤ A maxb αb gives the asymptotic claim. Measured aggregation opportunity. Corollary 7.3 is active in the production regime. The measured lane-update/group-update factor averaged only 1.00284 at |Π| = 4096, 1.00071 at |Π| = 16384, and 1.00018 at |Π| = 65536; over the full matrix it was 1.00124 (maximum 1.00622). Thus warp grouping is an exactness-preserving implementation option but provides no material reduction for this wide, collision-sparse namespace. It must not be credited with the throughput gain of the counter-bank pilot below. Proposition 7.4 (Sharded exact counter banks). Let s be a power of two and assign each warp w to a bank h(w) ∈ {0, . . . , s − 1}. Replace the packet and byte counter for block b by banked counters byte pkt . A warp class for b updates only bank h(w), and the scenario result is and Cb,j Cb,j I pkt (b) =
s−1 X
pkt Cb,j ,
I byte (b) =
j=0
s−1 X
byte Cb,j .
j=0
The banked accumulator is exact under every interleaving, uses O(s|Π|) counters, and adds O(s|Π|) deterministic reduction work per scenario. For a fixed block, updates issued by warps in different banks cannot serialize on the same address. Proof. Each warp class contributes to exactly one bank of its target block. The banks therefore partition the multiset of contributions to b. Summing them recovers the unbanked packet count and byte sum by associativity and commutativity. There are two arrays of s|Π| counters and two length-s reductions per block. Distinct banks occupy distinct addresses, proving the final claim. Counter-bank crossover pilot. The bank count was fixed before the production matrix by a controlled two-device crossover at |Π| = 4096, r = 1, and q = 0.5. Each 30-second run used the same seed and 41 GiB replay buffer; the second round exchanged the one-bank and 32-bank assignments between the two devices. Mean throughput was 20.13 Gpacket/s with one bank and 21.25 Gpacket/s with 32 banks, a factor of 1.055 (5.54%). Complete JSON records and progress logs for all four runs are retained in the optimization checkpoint. This pilot selects the implementation parameter; it is not included in the production matrix or Table 1.
9
Theorem 7.5 (Seeded exact-stratified residency index). Let the hot and cold block classes each have size H = 2h . For class j, derive an odd aj and offset cj from the scenario seed and define φj (x) = (aj x + cj ) mod H. For target fraction q, mark local block x resident iff φj (x) < k, where k = round(qH). The index uses O(1) words, answers membership in O(1) time, and places exactly k resident blocks in each class. Its realized resident fraction is k/H, at distance at most 1/(2H) from q. If the route-draw masses of the classes sum to one, their total resident probability mass is exactly R = k/H. Proof. Multiplication by odd aj is invertible modulo 2h ; adding cj preserves bijectivity. Hence precisely the k preimages of {0, . . . , k − 1} are resident. The arithmetic stores only (aj , cj , k) and takes constant time. Rounding gives |k/H − q| ≤ 1/(2H). Both classes have resident fraction k/H, so weighting them by class masses that sum to one gives R = k/H. Proposition 7.6 (Expected impact under route draws). Suppose each of the r route draws independently chooses block b with probability πb , repeated parents are deduplicated, and the resident set is fixed. Put X R= πc . c:zc =1
For a resident block b, the expected packet impact over N unit-weight packets is E[I(b)] = N [(1 − R + πb )r − (1 − R)r ] . In the two-temperature experiment, πb = 1.8/|Π| for a hot block and πb = 0.2/|Π| for a cold block. Hence, for r = 1, every resident cold block has expected impact 0.2N/|Π|, independently of the realized resident set. Proof. Block b is the unique resident parent exactly when every draw avoids the resident blocks other than b, but not every draw avoids b as well. The first event has probability (1−R+πb )r and the nested second event has probability (1 − R)r . Their difference is the per-packet loss probability; linearity of expectation gives the result. Substituting the two route masses proves the final statement. Corollary 7.7 (Service-scale separation). Consider a sequence of two-hop instances with fixed redundancy r and block count B = |Π|. Suppose the resident probability mass is RB and every block atom satisfies maxb πb = O(1/B). If a resident block b has πb = βb /B + O(B −2 ), then E[I(b)] r(1 − RB )r−1 βb = + O(B −2 ). N B The zero-resident service fraction is exactly (1 − RB )r , while the exactly-one-resident fraction is rRB (1 − RB )r−1 + O(B −1 ). Thus enlarging the block namespace leaves aggregate service-state probabilities stable up to finiteatom corrections, but dilutes each coordinate of the impact vector as 1/B. In the two-temperature experiment, quadrupling B should therefore quarter per-block impact to first order. Proof. The first display is the Taylor expansion of Proposition 7.6 in the atom πb : (1 − RB + πb )r − (1 − RB )r = r(1 − RB )r−1 πb + O(πb2 ). 10
Substituting πb = βb /B + O(B −2 ) gives the coordinate claim. A packet has no resident parent iff all r draws avoid the resident probability mass, giving (1 − RB )r exactly. The exactly-one-resident probability is the sum of the coordinate probabilities over resident blocks.PSumming the linear terms gives rRB (1 − RB )r−1 ; the remainder is bounded by a constant times b:zb =1 πb2 ≤ RB maxb πb = O(B −1 ). Proposition 7.8 (Zero-impact extreme-value threshold). Fix one demand class containing m resident blocks with the same per-packet impact probability ζ. Let Xb be the impact count of block b after N independent packets, let µ = m(1 − ζ)N .
Z = {b : Xb = 0} , Then E[Z] = µ and
µ ≤ Pr min Xb = 0 ≤ min{1, µ}. b 1+µ
Thus the minimum coordinate undergoes a finite-stream transition near N ζ = log m: more precisely, µ = m exp −N ζ + O(N ζ 2 ) . Coordinate-wise 1/|Π| scaling can therefore coexist with an abrupt collapse of the observed minimum to zero when the namespace grows at fixed stream length. Proof. For each resident b, Xb has marginal distribution Bin(N, ζ), so Pr[Xb = 0] = (1 − ζ)N and linearity gives E[Z] = µ. A packet cannot contribute unique-resident impact to two different blocks. Hence, for b ̸= c, Pr[Xb = Xc = 0] = (1 − 2ζ)N ≤ (1 − ζ)2N , P so the zero indicators have nonpositive pairwise covariance and Var(Z) ≤ b Var(1[Xb = 0]) ≤ µ. Markov’s inequality gives Pr[Z > 0] ≤ min{1, µ}. The second-moment inequality gives Pr[Z > 0] ≥
E[Z]2 µ2 µ ≥ = . E[Z 2 ] µ + µ2 1+µ
Finally, expanding log(1 − ζ) = −ζ + O(ζ 2 ) gives the threshold form. Proposition 7.9 (Finite-stream deviation envelope). Fix one generated scenario and let ζb = (1 − R + πb )r − (1 − R)r be the per-packet expected impact probability from Proposition 7.6. Let Xb be the stored packet-impact counter for resident block b. For each demand class C define the observed envelope ∆C =
max |Xb − N ζb |.
b∈C:zb =1
Then every additive block-price query Q ⊆ Π satisfies the deterministic bound X b∈Q:zb =1
Xb − N
X
ζb ≤
X
|Q ∩ C ∩ {b : zb = 1}| ∆C .
C
b∈Q:zb =1
Consequently, if two candidate sets have an expected additive-price gap larger than the sum of their two right-hand sides, the finite stream cannot reverse their ordering. 11
Proof. For each resident block b in class C, the definition of ∆C gives |Xb − N ζb | ≤ ∆C . Summing this coordinate-wise inequality over the resident members of Q and applying the triangle inequality proves the displayed bound. Applying the same bound to two candidate sets shows that an expected gap larger than both possible deviations cannot change sign after replacing expectations by observed counters. Storing every generated packet would make the artifact scale with N , although the evaluation consumes only additive statistics. A counter-based generator names packets without materializing the stream, following the standard parallel-reproducibility pattern [14]. The implementation applies the SplitMix64 mixing function [15] to the seed–counter pair; it is used for deterministic synthetic generation, not for cryptography. Let gθ,s (i) be the packet generated from configuration θ, seed s, and counter i. Theorem 7.10 (Replay-compressed exactness). Let (M, ⊕, 0) be a commutative monoid and ϕ map one generated packet to its contribution in M . For a counter interval [a, a + N ) define A(θ, s, a, N ) =
a+N M−1
ϕ(gθ,s (i)).
i=a
The record (θ, s, a, N, A) is sufficient to reproduce the complete packet stream and to recover exactly every reported metric that factors through A. It stores a constant number of records rather than N packet records; its bit complexity is O(|θ| + |s| + log a + log N + size(A)) , and replay takes O(N ) generator evaluations. Concatenating adjacent intervals requires only monoid addition of their summaries. Proof. The generator is a deterministic function of (θ, s, i), so enumerating the stored interval reconstructs each packet in order. A metric that factors through A depends only on the displayed monoid fold and is therefore unchanged when the raw stream is replaced by its summary. Encoding the interval endpoints needs logarithmically many bits, and the tuple contains no per-packet term, establishing the size bound. For adjacent intervals, associativity gives A[a, c) = A[a, b) ⊕ A[b, c). Theorem 7.11 (Exact-summary lower bound). Let B = |Π| ≥ 2. Even in the two-hop case with one parent per packet and every block resident, any deterministic summary that answers the exact packet impact of every block after a stream of N packets requires at least N +B−1 log2 B−1 bits in the worst case. Storing the complete impact vector uses at most B⌈log2 (N + 1)⌉ bits. Proof. With one resident is any nonnegative integer vector P parent per packet, the impact vector N +B−1 (x1 , . . . , xB ) satisfying b xb = N . Stars and bars gives B−1 such vectors. A summary from which every coordinate is recovered exactly must assign different states to different vectors, giving the logarithmic lower bound. Each coordinate lies in {0, . . . , N }, so B fixed-width counters give the upper bound.
12
The summary monoid contains two |Π|-dimensional impact vectors, packet and byte totals, counts with zero, one, or multiple resident parents, and two 64-bit replay fingerprints. The fingerprints are integrity checks rather than substitutes for exact counters. The ancillary artifact additionally stores 2,048 evenly spaced decoded packet records per scenario, full per-block impact vectors, progress logs, five-second device telemetry, source and binary hashes, independent validation output, and the deviation envelopes of Proposition 7.9. Appendix A specifies the binary format and verifier.
7.1
Experimental protocol
Two-stage design. An initial Bernoulli-residency calibration ran nine five-minute scenarios before checkpointing. It processed 37.24 trillion packets (25.86 PiB of simulated payload) over 0.75 aggregate GPU-hours and exposed seed-to-seed variation in resident count and resident probability mass. Its complete vectors, telemetry, progress logs, and validation report remain in the ancillary checkpoint. The production stage replaces Bernoulli membership with Theorem 7.5 and enlarges the matrix to |Π| ∈ {4096, 16384, 65536}, path redundancy r ∈ {1, 2, 4, 8}, and target resident fraction q ∈ {0.50, 0.70, 0.90}. Parent demand follows a controlled two-temperature mixture: one half of the blocks receives 90% of route draws and the other half receives 10%. Thus R is fixed by (|Π|, q) rather than by seed, while seeds still vary route draws and victim metadata. Each of the 36 configurations has four seed replicates. The 144 scenarios are deterministically sharded over three NVIDIA L40 devices; each scenario runs for five minutes and each process allocates 41 GiB for the replay buffer. Warp classes are aggregated according to Proposition 7.2, then written through the 32-bank layout of Proposition 7.4. Impact pricing is compared with synthetic snapshot LRU, FIFO, and fixedseed random total orders generated independently of the measured demand topology. These orders instantiate the topology-oblivious class in Definition 6.6; they are not executions of cache policies against an external request trace. Each deterministic total order is realizable by an appropriate prehistory, but that pre-history is not inferred from the evaluation stream. Consequently the reported ratio is a controlled topology-information gap under this generator, not a claim that deployed LRU or FIFO incurs the same factor. For an order’s victim p, the ratio is (I(p) + 1)/(Imin + 1), with a one-packet pseudocount only to define zero-impact cases; ratios are aggregated across replicates by the geometric mean. Hardware telemetry is sampled every five seconds. The complete matrix is reported in one table after every selected victim has been checked against the stored per-block vectors.
13
Table 1: Complete replay-compressed GPU matrix. Each row aggregates four five-minute seed replicates. Pkt is the packet count in trillions and traffic is simulated payload in PiB. q is the target resident fraction enforced separately in the hot and cold halves by an exact affine permutation; n is the completed replicate count. U0 and U1 are packets with zero and exactly one resident parent. Imin is minimum packet impact per billion packets. Synthetic topology-oblivious order entries give geometric-mean damage relative to minimum impact; they are not deployment trace replays. Perseed minima and maxima remain in the ancillary CSV. Hardware columns are five-second telemetry means except Tmax . Topology |Π| r
Scale
Service/impact
Damage ratio
L40 telemetry
q [n] Pkt (T) traffic (PiB) Gpkt/s U0 (%) U1 (%) Imin (ppb) LRU FIFO random GPU (%) VRAM (GiB) 50.000 29.980 10.010 25.000 8.988 1.002 6.250 0.808 0.010 0.391 0.007 0.000
W Tmax (◦ C)
4,096 1 4,096 1 4,096 1 4,096 2 4,096 2 4,096 2 4,096 4 4,096 4 4,096 4 4,096 8 4,096 8 4,096 8
0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4]
24.54 22.24 20.56 18.89 19.25 21.05 13.88 14.46 14.95 8.69 8.73 8.77
17.05 15.45 14.28 13.12 13.37 14.62 9.64 10.04 10.38 6.04 6.07 6.09
20.44 18.52 17.13 15.73 16.03 17.53 11.56 12.04 12.45 7.23 7.27 7.29
50.000 70.020 89.990 50.020 42.012 18.052 25.030 7.562 0.363 3.134 0.123 0.000
48818.812 48817.810 48817.306 48819.689 29272.104 9772.780 24408.992 5260.150 195.256 3048.969 84.417 0.026
5.20 1.73 3.00 5.20 3.00 5.21 1.73 9.02 1.74 1.74 5.26 2.62
3.00 1.73 3.00 1.73 1.73 1.73 1.73 1.73 5.24 1.74 1.75 7.90
1.73 5.20 5.20 5.20 3.00 1.73 3.00 3.01 5.24 3.01 1.75 4.54
100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
41.46 291.5 41.46 294.3 41.46 293.4 41.46 297.3 41.46 293.8 41.46 294.3 41.46 298.2 41.46 297.4 41.46 297.6 41.46 298.1 41.46 298.7 41.46 298.5
69 71 70 71 72 71 73 74 74 73 75 76
16,384 1 16,384 1 16,384 1 16,384 2 16,384 2 16,384 2 16,384 4 16,384 4 16,384 4 16,384 8 16,384 8 16,384 8
0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4]
24.02 22.08 20.44 18.88 19.10 20.97 13.81 14.38 14.78 8.66 8.68 8.76
16.68 15.33 14.20 13.11 13.26 14.57 9.59 9.99 10.26 6.02 6.03 6.08
20.01 50.000 50.000 18.39 30.005 69.995 17.02 9.998 90.002 15.72 25.000 50.005 15.90 9.003 42.011 17.46 1.000 18.005 11.50 6.250 25.008 11.97 0.811 7.567 12.31 0.010 0.360 7.21 0.391 3.127 7.23 0.007 0.123 7.29 0.000 0.000
12202.111 12201.181 12200.807 12201.459 7320.851 2438.391 6098.958 1316.693 48.353 760.660 20.994 0.003
1.73 3.00 1.00 5.20 1.73 5.20 3.00 3.01 1.01 3.01 3.06 7.83
5.20 3.00 5.20 1.00 1.73 3.00 3.00 5.21 3.03 1.00 3.06 5.30
3.00 5.20 5.20 3.00 5.20 1.73 1.73 1.74 3.03 5.22 9.17 8.20
100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
41.46 291.8 41.46 292.9 41.46 293.2 41.46 294.6 41.46 293.9 41.46 294.6 41.46 298.1 41.46 297.9 41.46 298.2 41.46 298.8 41.46 298.3 41.46 298.6
72 72 70 72 72 73 72 75 75 74 74 75
65,536 1 65,536 1 65,536 1 65,536 2 65,536 2 65,536 2 65,536 4 65,536 4 65,536 4 65,536 8 65,536 8 65,536 8
0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4] 0.5 [4] 0.7 [4] 0.9 [4]
23.94 21.87 20.23 18.88 18.99 20.40 13.74 13.96 14.47 8.52 8.62 8.71
16.63 15.19 14.05 13.11 13.19 14.17 9.54 9.69 10.05 5.92 5.99 6.05
19.95 18.22 16.85 15.72 15.82 16.99 11.44 11.62 12.05 7.09 7.18 7.25
50.000 29.999 10.001 25.000 8.999 1.000 6.250 0.810 0.010 0.391 0.007 0.000
50.000 70.001 89.999 50.001 42.001 18.003 25.002 7.560 0.360 3.126 0.122 0.000
3048.868 1.00 3.00 3048.514 3.00 1.73 3048.526 5.20 1.73 3048.701 3.00 3.00 1828.566 3.00 3.00 609.013 1.00 3.01 1523.330 5.21 1.00 328.328 5.22 9.03 11.959 5.31 1.77 189.430 1.01 1.74 5.139 1.04 5.39 0.000 11.17 20.32
5.20 9.01 3.00 3.00 5.20 3.01 3.01 3.01 3.06 1.01 3.12 28.86
100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
41.46 292.4 41.46 294.6 41.46 293.9 41.46 303.5 41.46 290.4 41.46 295.1 41.46 297.6 41.46 298.7 41.46 298.2 41.46 297.6 41.46 298.9 41.46 298.0
72 71 70 73 72 72 74 74 74 76 76 75
Completed total / mean
582.90
404.86
13.48
–
–
–
100.0
41.46 296.2
76
–
14
–
–
Results. The three GPUs processed 582.90 trillion packets, representing 404.86 PiB of simulated payload and 8482.36 TiB under explicit 16-byte counter–event materialization. Mean throughput was 13.48 Gpacket/s per configuration (range 7.09–20.44). The cold-class prediction of Proposition 7.6 had mean absolute relative error 0.0128% and maximum error 0.1609%. Across the 36 configurations, the synthetic topology-oblivious orders labelled LRU, FIFO, and fixed-seed random had geometric-mean damage 2.92×, 2.76×, and 3.66× relative to the minimum-impact victim. These are controlled information-gap measurements under the generator, not deployment trace comparisons. The largest per-seed ratios were 53.00×, 48.00×, and 51.00×, respectively. Scale separation. The block-scale comparison from |Π| = 16,384 to |Π| = 65,536 tests Corollary 7.7 at fixed redundancy and resident fraction. The per-coordinate minimum-impact ppb ratio over the 11 pairs with nonzero measured minima at both scales averaged 0.2490 (range 0.2448– 0.2499), close to the first-order quartering predicted by the 1/|Π| atom mass. The remaining pair entered the finite-count tail: at r = 8, q = 0.9 the larger system contained a zero-impact empirical minimum, so no ratio was assigned. Across the same pairs, zero- and single-resident service fractions changed by at most 0.0101 percentage points; the aggregate service state is therefore nearly scale-invariant while individual eviction coordinates dilute. Finite-count minimum transition. The only zero-impact coordinates occurred in the cold |Π| = 65, 536, r = 8, q = 0.9 class. Its coordinate mean was only 5.28–5.40 packets, while each frame contained 29,491 resident cold coordinates. Proposition 7.8 therefore predicts 132.7–149.8 zero coordinates per frame and gives a per-frame lower bound 99.25% on a zero minimum. All four frames crossed the threshold, with 120–145 zeros each (532 observed versus 578 expected in total). At the preceding |Π| = 16, 384 scale the coordinate mean remained 21.25–21.68, the per-frame zero-minimum upper bound was at most 4.34 × 10−6 , and no zero occurred. This extreme-value transition, rather than a failure of the coordinate expectation, explains the single scale pair whose minimum-impact ratio is undefined. Device utilization. Five-second telemetry recorded mean GPU utilization 100.0%, mean allocated memory 41.46 GiB per device, and mean board power 296.2 W; the maximum observed temperature was 76◦ C. These measurements are retained as observations rather than folded into the replay summary. Warp aggregation reduced the number of global packet/byte impact update pairs by only 0.124% on average (maximum 0.622%), confirming the collision-sparse regime of Corollary 7.3. It preserved both conservation identities but supplied no material production benefit; the separately measured 5.54% crossover gain belongs to 32-bank sharding. The finite-stream deviation verifier found maximum resident-cardinality rounding error 0.80 blocks (0.000195 of the block set), mean absolute coordinate-level theory error 1.1725%, and maximum normalized residual 5.95 standard-error units over 2,890,144 resident coordinates. In the class containing that maximum, the RMS normalized residual was 1.000 and the 95th percentile was 1.977. The largest relative percentage error occurred in the |Π| = 65536, r = 8, q = 0.9 cold class, where the expected impact was only 0.0024 ppb; the verifier therefore reports it as a finite-count tail effect rather than as a resident-mass error.
15
8
Confluent invalidation and a replicated index
Invalidation drops residency from a seed and forwards that change across transfer links. To model asynchronous propagation as a replicated index, fix S ⊆ V and let F (X) = X ∪ { v ∈ V : ∃u ∈ X, u → v ∈ E }. Theorem 8.1 (Confluence and coordination-freeness). The invalidated states ordered by inclusion form a join-semilattice under ∪, on which F is monotone and inflationary; its least fixed point above S is the forward-reachable set R = {v : v is E-reachable from S}. Every fair execution from S, under any order, batching by union, or duplication, eventually stabilizes at R. Invalidation is therefore confluent and coordination-free in the sense of monotone eventual consistency. Proof. The join ∪ is commutative, associative and idempotent, so the states form a join-semilattice; F and inflationary, so by the Knaster–Tarski theorem [9] it has least fixed point S is monotone n (S) = R above S. Any execution adds only nodes of R (a new node has an invalidated F n≥0 in-neighbour, inductively in R), and fairness adds every node of R (each has a predecessor added first along a shortest path). Idempotence makes duplication and reordered batching immaterial. Monotonicity with the semilattice structure is exactly the condition for coordination-free convergence [10, 12, 11]; an invalidated location is a tombstone, moving only upward in the order. Theorem 8.2 (Delta-state replicated index). Represent each replica’s invalidated set as a grow-only set and propagate deltas, the newly invalidated identifiers, by the join ∪. Under fair asynchronous delivery, every replica eventually converges to R, despite reordering or duplication. If the replica overlay has diameter d and a synchronous round delivers across every overlay edge, convergence occurs within d rounds after the last new identifier is introduced. The payload emitted by a replica in one round is bounded by the identifiers newly added since its previous emission. Proof. A grow-only set under ∪ is a state-based CRDT whose merges are commutative, associative and idempotent [12, 13]. Fair delivery eventually carries every delta to every replica, so all states converge to their global join, which is R by Theorem 8.1. No finite bound follows for an arbitrary asynchronous schedule: fairness may delay a message for an unbounded time. Under the stated synchronous full-edge schedule, an identifier advances at least one edge per round and reaches every replica along a shortest path of length at most d. Sending only additions gives the payload bound. Theorem 8.2 supplies order-independence and bounded delta payloads for eventual invalidation. Certificates computed before convergence are local snapshots; after every replica has joined all deltas they agree on the stable set R.
9
Recoverable versus irrecoverable eviction
Eviction is of two kinds. A recoverable eviction demotes a block to a slower tier from which it can be reloaded; an irrecoverable one releases the block for reuse and is absorbing. The origin remains resident. A configuration is therefore a block map γ : Π −→ {res, rec, free}. The operations demote(Q), reload(Q), and free(Q) act on a set of blocks Q ⊆ Π: demotion maps res to rec, reload maps rec to res, and free maps either non-free state to free. Reload ignores freed blocks and free is absorbing. 16
Theorem 9.1 (Reinstatement lattice). Let γ0 be a block configuration. (1) (Recoverable regime.) If γ0 has no freed block and no schedule uses free, the reachable configurations are exactly {res, rec}Π , a Boolean lattice under the blockwise order res < rec. Full residency is reached by reload(Π), and reachability of a block-aligned target configuration is decidable in O(|Π|). (2) (Irrecoverable regime.) The set of freed blocks is nondecreasing along every schedule and equals the initial freed set union the cumulative free domain. A block is reloadable iff it is currently recoverable, and entry into the freed set is permanent. Proof. (1) With no free operation, each block automaton has both transitions between res and rec, independently of the other blocks. Hence the reachable set is the stated product lattice, and one reload over all blocks reaches full residency. (2) Free only adds blocks to the freed set and no transition removes them. Thus after a schedule with cumulative free domain D, the freed set is Free(γ0 ) ∪ D, and every freed block remains fixed. The recoverable regime keeps full block residency within reach; an irreversible release removes that block from every future resident configuration. Expressing the automaton over Π, rather than over individual locations, preserves alignment by construction.
10
Discussion
The static decision contract is exact. For one candidate, two reachability forests and their closed boundaries certify the demand removed by that block. For a two-hop network, the same quantity reduces to a streaming sufficient statistic and all candidates can be accumulated together. These are different complexity statements and should not be merged: the accelerated result does not imply a one-pass all-candidate algorithm for arbitrary directed graphs. The replay record also has a precise scope. It is lossless for the generated packet stream and for metrics that factor through the stored monoid summary. It does not make wall-clock timing deterministic; timing and device state are measured observations and are retained separately as result records and telemetry. The two fingerprints detect accidental disagreement but are not used as a proof of equality. Equality of the reported impact metrics is checked against the complete stored vectors and conservation identities. Scope and limits. The k-competitive statement is confined to the block-reference paging specialization. Path admission, weighted retrieval, and fully dynamic directed reachability require additional algorithms; this paper claims re-traversal for a general fixed candidate and a one-pass kernel only for the two-hop case. The hardness theorem concerns unweighted block actions with protected terminals. The experimental networks are synthetic and deliberately controlled. In particular, the rows labelled LRU, FIFO, and random are topology-independent total orders, not cache policies replayed against a deployment trace. Their ratios quantify the value of topology information under the stated generator; they do not estimate a universal deployment penalty for LRU or FIFO. Warp aggregation is likewise an exact transformation rather than an empirical speed contribution in this regime: the measured reduction is only 0.124% on average, whereas the separate 32-bank crossover accounts for the 5.54% pilot gain. Fair asynchronous gossip has no finite convergence-time bound; the diameter guarantee applies only to synchronous full-edge rounds.
17
Open empirical questions. The controlled separation identifies three measurements needed from operational networks. First, how strongly are recency and insertion history correlated with service-cut impact, and when does that correlation make a topology-oblivious order competitive in practice? Second, what target concentration or namespace size makes warp grouping worthwhile, and can a runtime choose among lane grouping, bank sharding, and direct atomics from an online collision estimate? Third, does the zero-impact threshold of Proposition 7.8 persist under bursty, dependent traffic, or does an extremal-index correction replace the independent-packet law? Answering these questions requires trace-linked topology and residency snapshots; the present artifact supplies the exact counters and verifier against which such traces can be compared.
11
Conclusion
Aligned eviction is a graph decision, not merely a recency decision. The paper supplies an independently checkable impact certificate, separates polynomial location cuts from hard block-action minimization, and gives a one-pass data structure for the two-hop case used in the accelerated study. Counter-based replay and exact additive summaries decouple experimental scale from archive size without discarding the candidate vectors, samples, logs, or telemetry needed for audit. The CRDT formulation handles invalidation order, while the state model keeps recoverable demotion distinct from irreversible release.
References [1] S. Ioannidis and E. Yeh. Adaptive caching networks with optimality guarantees. IEEE/ACM Transactions on Networking, 26(2):737–750, 2018. [2] I. Baev, R. Rajaraman, and C. Swamy. Approximation algorithms for data placement problems. SIAM Journal on Computing, 38(4):1411–1429, 2008. [3] K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10:96–115, 1927. [4] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. [5] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972. [6] R. M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer. Certifying algorithms. Computer Science Review, 5(2):119–161, 2011. [7] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202–208, 1985. [8] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. [9] A. Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285–309, 1955. [10] J. M. Hellerstein and P. Alvaro. Keeping CALM: when distributed consistency is easy. Communications of the ACM, 63(9):72–81, 2020.
18
[11] T. J. Ameloot, F. Neven, and J. Van den Bussche. Relational transducers for declarative networking. Journal of the ACM, 60(2):15:1–15:38, 2013. [12] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. In Proc. SSS, LNCS 6976, pages 386–400. Springer, 2011. [13] P. S. Almeida, A. Shoker, and C. Baquero. Delta state replicated data types. Journal of Parallel and Distributed Computing, 111:162–173, 2018. [14] J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw. Parallel random numbers: as easy as 1, 2, 3. In Proc. International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 1–12, 2011. [15] G. L. Steele, Jr., D. Lea, and C. H. Flood. Fast splittable pseudorandom number generators. In Proc. ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 453–472, 2014.
A
Accelerated streaming algorithm and audit artifact
A.1
Exact-stratified residency
Algorithm A.1: constant-state residency membership. 1: Split the B blocks into hot and cold classes of size H = B/2, where H is a power of two. 2: For each class derive an odd multiplier a and offset c from the scenario seed. Store these four words and k = round(qH). 3: For queried block b, compute its class and local index x, then rank y = (ax + c) & (H − 1). 4: Return resident iff y < k. Because a is odd, the rank map is a permutation and each class contains exactly k resident blocks.
A.2
Streaming accumulator
The implementation uses 64-bit unsigned counters. The verifier checks 64 2 −1 N≤ , 64N ≤ Btotal ≤ 1500N, 1500 so neither a packet counter nor a byte counter can overflow under the encoded packet-size range. It also checks that no per-block impact exceeds the corresponding stream total. Parent identifiers are deduplicated before the resident-parent count is taken; without this step two equal route draws would be mistaken for path redundancy. Algorithm A.2: one scenario on one device. 1: Zero the 32 packet-impact banks, 32 byte-impact banks, service-state totals, and replay fingerprints. At the maximum |Π| = 65,536, the two bank arrays occupy exactly 2 · 65,536 · 32 · 8 = 32 MiB. 2: Until the five-minute deadline, launch a counter kernel over the 41 GiB buffer. At position j, write gθ,s (a + j) and advance the global counter interval after the pass. 19
3: In parallel for each generated packet, derive at most r parent blocks, remove duplicate parents, and evaluate the deterministic residency predicate for each distinct parent. 4: If no parent is resident, increment the unserved counter. If exactly one parent b is resident, group warp lanes by b, map the warp to one of 32 banks, then let one lane atomically add the group size and group byte sum to that bank of b. Otherwise increment the multiply-served counter. 5: Fold the packet count, byte count, and two 64-bit fingerprints into the scenario summary using atomic commutative operations. 6: Synchronize once per buffer pass. At the deadline, reduce each block’s 32 banks in a deterministic kernel, then copy the two impact vectors and scalar summary to the host. 7: Among resident blocks, select the minimum packet-impact victim. Select LRU, FIFO, and random victims from topology-independent deterministic metadata. 8: Append one JSON result, one binary detail frame, and 2,048 evenly spaced decoded audit samples; flush both files before starting the next scenario.
A.3
Canonical binary detail frames
Each device first writes one canonical little-endian detail stream. Keeping this measurement path uncompressed isolates the timed kernel from the artifact codec. The file begins with the eightbyte magic string AEIMPACT, a schema number, an endian marker, and the audit-sample count. Every schema-3 scenario frame then stores a tag; scenario and repetition identifiers; block count, redundancy, and occupancy; seed and half-open counter interval; packet and byte totals; both fingerprints; the exactly-one-parent byte total; the number of warp-aggregated impact groups; the complete packet-impact vector; the complete byte-impact vector; and 2,048 audit triples. An audit triple contains the counter, generated 64-bit event, and packed decoded metadata (packet bytes, live-parent count, and the sole parent identifier or a sentinel when that count is not one). The frame size is exactly 4 + 5(4) + 9(8) + 16|Π| + 2048(24) = 49,248 + 16|Π| bytes. Across four replicates of the 3 × 4 × 3 matrix, the detail streams therefore occupy 144(49,248) + 16 · 48(4096 + 16384 + 65536) = 73,152,000 bytes, plus three 24-byte file headers. This bound includes every candidate impact and all 294,912 decoded audit records before lossless coding. The 50,000,000-byte ancillary budget is checked over the implementation, logs, calibration checkpoint, production vectors, telemetry, and validation output together.
A.4
Reconstructible lossless artifact codec
The production streams also have a compact representation, identified by the eight-byte magic string AECODEC1. The transformation is performed after measurement and is exactly reversible to the schema-3 frame. It exploits two invariants already checked by the verifier rather than discarding observations.
20
Residency-conditioned vector coding. For either impact vector x ∈ {0, . . . , 264 − 1}|Π| , every nonresident coordinate is zero. In each of the hot and cold classes, let m be the lower median of the resident coordinates. Resident coordinates are visited in increasing block order and represented by ( 2d, d ≥ 0, db = xb − m, zz(d) = −2d − 1, d < 0, followed by unsigned LEB128 coding of zz(db ). The two medians are stored as 64-bit values. A high bit in each payload-length field selects a fixed-width fallback: if the residual payload is not shorter than the original vector, the codec stores that vector verbatim. Thus the choice is made independently for packet and byte impacts and cannot expand either vector payload. Seed-indexed audit coding. For sample index j ∈ {0, . . . , K − 1}, K = 2048, the canonical counter is (2j + 1)(b − a) cj = a + 2K for scenario interval [a, b), and the event is gθ,s (cj ). The codec therefore stores only the eight-byte packed metadata for each sample. The decoder reconstructs both the counter and event exactly from the frame fields and restores the original 24-byte audit triple. Theorem A.1 (Byte-exact decodability). For every valid schema-3 frame, the artifact codec reconstructs the complete packet-impact vector, byte-impact vector, and every audit triple byte for byte. The encoding is injective on valid frames. Its fixed per-frame cost is 16,552 + Lpkt + Lbyte bytes, where each L is the smaller of its residual payload and the corresponding 8|Π|-byte fixed-width vector. Consequently a coded frame is at most 16,552 + 16|Π| bytes, saving at least 32,696 bytes relative to its canonical schema-3 frame. This guarantee is independent of outer ZIP compression. Proof. The seed and exact-stratified predicate identify every resident coordinate; all remaining coordinates are zero by the one-pass update rule. ULEB128 is prefix-decodable, ZigZag is a bijection from signed integers to nonnegative integers, and adding the stored class median inverts the residual transform. The fixed-width mode is the identity. The displayed sample formula and deterministic generator reconstruct the two omitted audit fields, while packed metadata is stored verbatim. Hence the decoder recovers the canonical field sequence uniquely. The coded fixed fields occupy 96 bytes, predictor and length fields 40 bytes, sample metadata 2048 · 8 = 16,384 bytes, and the frame digest 32 bytes, totaling 16,552 bytes before vector payloads. Each adaptive payload is no larger than 8|Π|, which proves the bound and the 32,696-byte saving against 49,248 + 16|Π|. Each coded frame carries SHA-256 of the reconstructed canonical frame. This digest is an error detector, not the reason the transform is lossless: injectivity follows from the explicit inverse above. The independent decoder first reconstructs schema-3 bytes and checks the digest, then applies the semantic conservation, victim, residency, and replay checks.
21
Pre-production size pilot. On the 36-configuration one-second matrix, the codec reduced the canonical detail stream from 18,288,024 to 3,643,748 bytes, a factor of 5.02, while the independent analyzer emitted an identical summary CSV. Deflate level 9 reduced the canonical and coded streams to 4,775,820 and 2,931,493 bytes, respectively; the codec therefore retained a further factor of 1.63 after outer compression. These figures characterize the artifact representation and are not used as performance results.
A.5
Independent validation
Algorithm A.3: artifact verifier. 1: Parse all JSON records and coded binary frames; reconstruct canonical schema-3 frames, check each SHA-256 digest, and reject duplicate or missing (scenario, repetition) keys and malformed counter intervals. 2: Match every scalar field and fingerprint in JSON against its binary frame. 3: Verify the conservation identity X Ipacket (b) = None , b∈Π
X
Ibytes (b) = Bone ,
b∈Π
because every packet with exactly one resident parent contributes its packet and byte weight to exactly one block and every other packet contributes to none. 4: Recompute the resident predicate for every block, take the minimum stored impact over resident candidates, and compare it with the reported impact-priced victim. 5: Look up each reported LRU, FIFO, and random victim in both stored impact vectors and compare its packet and byte values with JSON. 6: For every audit sample, regenerate the event from its seed and counter, reconstruct distinct parents, residency, packet size, live-parent count, and sole parent, then compare the packed metadata bit for bit. 7: Aggregate repetitions only after all checks pass. Emit the CSV used by Table 1 and a machine-readable validation report.
A.6
Deviation-envelope extraction
The verifier also emits deviation_summary.csv and deviation_report.json. These files are derived from the same reconstructed impact vectors used for victim validation; no additional measurement path is introduced. The purpose is to separate four effects that are otherwise easy to confuse: resident-cardinality rounding in Theorem 7.5, finite-stream route variation around Proposition 7.6, extreme-value collapse of the minimum in Proposition 7.8, and genuine policy damage relative to the impact-priced victim. Algorithm A.4: deviation-envelope verifier. 1: For each validated frame, recompute the exact resident set and resident probability mass R from the stored seed, block count, and occupancy. 2: For every resident block b, compute ζb = (1 − R + πb )r − (1 − R)r and residual eb = Xb − N ζb from the stored packet-impact vector. 22
3: Aggregate residuals separately for the hot and cold classes. For each class write the mean observed ppb, theory ppb, signed relative error, mean and maximum absolute relative error, and the envelope ∆C = max |eb | both in packets and ppb. p 4: Also write normalized coordinates eb / N ζb (1 − ζb ) when ζb > 0. These values are diagnostics for finite-count scale; the artifact treats the exact residual envelope, not a distributional assumption, as the certificate. 5: Count zero-impact coordinates in each class and compute µC = mC (1−ζC )N , the probability bracket in Proposition 7.8, and the threshold margin N ζC − log mC . 6: Record the realized resident fraction and its deviation from the target q. Because each class rounds independently, the total resident-count error is at most one block and the fraction error is at most 1/|Π|. 7: Emit a compact JSON summary containing the worst relative coordinate error, worst normalized residual, total resident-coordinate count, zero-minimum transition, maximum residentcardinality rounding error, and maximum class envelope. The generated findings paragraph reads this JSON after the full 144-scenario matrix validates.
A.7
Ancillary evidence
The ancillary files contain the implementation, reconstructible exact impact vectors, audit-sample metadata, telemetry, build and progress logs, manifests, validation output, and deviation summaries. Production detail streams use the byte-exact AECODEC1 representation; the Bernoulli calibration checkpoint remains in its original schema. The packet stream itself is represented by generator parameters and counter intervals as specified by Theorem 7.10. Validation reconstructs every canonical frame, checks its digest and semantic invariants, and verifies the recorded file hashes.
23