Coded caching lets a server send one broadcast that satisfies several users at once. Each user stores pieces of many files ahead of time. At request time the server sends combinations of pieces, typically bitwise XORs, and each user cancels out the pieces it already holds. The catch is that each file must be cut into a very large number of sub-packets, a cost called subpacketization. Practical schemes keep that number manageable through rigid combinatorial layouts called placement delivery arrays, which are tables saying which user stores which sub-packet and which sub-packets get XORed together. All of these schemes assume the files never change. Meanwhile, the literature on balancing freshness against cost studies caches of content that does change: how often to refresh, push versus pull, age-of-information policies. That literature assumes every transfer is uncoded. Real edge content such as news, maps, or sensor dashboards both changes and is requested by many users at once, so neither body of work describes it.
This note proposes a simple but consequential change of viewpoint. The placement array is never rebuilt. It becomes a fixed "address book" of which users hold which byte ranges of each file. An update to a file then becomes a sub-packet-level refresh, which the server multicasts once to exactly the users the array lists as holders. Because the server knows every holder's version, the freshness question reduces to one decision per sub-packet: refresh off-peak, where it is cheap but possibly wasted if the file changes again, or correct stale holders at delivery time, where it is expensive but paid only when a request needs it. Subpacketization then stops being a pure hardware nuisance. It sets how finely a partial edit can be refreshed, which yields an interior optimal number of sub-packets even before hardware limits apply.
Core Claim
Coded multicast delivery and freshness control can be separated cleanly over a fixed array, with one condition: the server keeps a per-sub-packet version ledger, so every XOR uses exactly the version each holder has. Under this separation, three things hold.
First, a stale cache never causes decoding failure. It only creates a correction cost, and that cost equals the refresh the server skipped.
Second, the optimal refresh rule is a per-file threshold of the push/pull type proven for uncoded caches in Optimal Push and Pull-Based Edge Caching For Dynamic Content. Here, however, the cost of one refresh is a function of the subpacketization level $F$ and of how local the edit is.
Third, $F$ should be chosen jointly with the refresh policy. It trades the coding gain and edit granularity that come with larger $F$ against the per-packet header and indexing overhead, which also grows with $F$.
The contrast with the closest work is direct. On Coding for Cache-Aided Delivery of Dynamic Correlated Content handles files that change between placement and delivery. It does so by building an augmented conflict graph at request time and coloring it greedily. It does not bound subpacketization, has no structured array, and does not decide when to refresh. Dynamic Coded Caching in Wireless Networks uses erasure codes across base stations with time-to-live eviction, not XOR multicasting, and its dynamics come from request burstiness rather than source updates. Our proposal keeps the deterministic, nearly free online indexing of arrays such as Placement Delivery Arrays from Combinations of Strong Edge Colorings and Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes. It adds the freshness control those papers lack.
The Cost Model
Consider a file of $S$ bytes split into $F$ sub-packets, with a header and index overhead of $h$ bytes per transmitted sub-packet. Suppose an update rewrites a contiguous fraction $\rho$ of the file. Then about $\rho F + 1$ sub-packets are touched. Each touched sub-packet is held by the user group the array specifies, and one multicast refreshes that whole group. The bytes needed to refresh one update are therefore
$$B(F) \approx \rho S + \frac{S}{F} + (\rho F + 1)\,h .$$
In this expression, $\rho S$ is the changed content itself. The term $S/F$ is the boundary waste from rounding the edit out to whole sub-packets. The last term is the header cost. Minimizing over $F$ alone gives $F^\star \approx \sqrt{S/(\rho h)}$, which follows from balancing the boundary-waste term against the header term.
The full design pairs this with the delivery rate $R(F)$ available within an array family. The Tang–Ramamoorthy linear-block-code family is the natural choice because it exposes an explicit trade-off between $F$ and $R$. The design then minimizes a long-run cost of the form
$$J = c_{\text{peak}}\,\big(R(F) + C_{\text{corr}}\big) + c_{\text{off}}\,C_{\text{push}} + w\,\bar{A},$$
where the terms are defined as follows. $C_{\text{corr}}$ is the bytes of delivery-time correction for stale holders. $C_{\text{push}}$ is the bytes of off-peak refresh. $c_{\text{peak}}$ and $c_{\text{off}}$ are the per-byte prices in the two periods. $\bar{A}$ is the average age of the version served to users, which is nonzero only if the operator accepts serving stale content, and $w$ is its weight.
Pushing pays $B(F)$ for every update. Lazy correction pays once for all the sub-packets touched since the last refresh, but at peak price. Combining these, the threshold structure of the uncoded push/pull analysis is expected to carry over, with the popularity-to-update ratio rescaled by $B(F)$.
Research Program
The first component is a proof that version-ledger delivery over any placement delivery array is exact.
The second component is a theorem characterizing the optimal per-file refresh rule under Poisson updates and Poisson or Weibull requests. The Weibull case is included because Pedersen et al. show that request burstiness alone changes whether dynamic policies help. The Poisson update case resolves their result against the push/pull papers: dynamic policies matter there because the source changes, not because requests are bursty.
The third component is a joint choice of $F$ and threshold. It covers single-file closed forms and a multi-file greedy rule that sorts files by refresh value per byte. This rule follows the separability argument of Dynamic Content Updates in Heterogeneous Wireless Networks.
The fourth component is a robustness extension. The original concern about version mismatch causing decoding failure only arises if a refresh multicast is lost. We therefore add per-group acknowledgments and quantify the cost of resending refreshes under loss.
We will build a packet-level simulator. It will include the Michel–Wang and Tang–Ramamoorthy array families, explicit headers, and the ledger.
Baselines
The naive reference is uncoded push/pull caching. Each user's cache is refreshed with whole-file unicasts under the optimal threshold policies of Optimal Push and Pull-Based Edge Caching For Dynamic Content, and delivery is uncoded. It is the strongest freshness-side competitor because its policy is provably optimal within the uncoded class. That paper's extracted summary gives no numerical cost values; no reported result found on Lacuna for its cost figures. We will therefore run it ourselves on identical update and request traces with the same peak and off-peak prices. Beating it means lower $J$ at equal served-version age whenever there are more than a few users.
The second baseline keeps a static array and serves any updated file by uncoded unicast. This is what a practitioner would deploy first. It keeps the array intact and needs no new theory. It is run on the same arrays and traces as our method.
The third baseline is CA-CACM, the strongest existing dynamic coded scheme. For context, it reports a 1.7x network-load reduction over correlation-unaware schemes with 90 correlated static files. It also reports performing 3x better than traditional methods when 60% of files update between placement and delivery (On Coding for Cache-Aided Delivery of Dynamic Correlated Content). We will reimplement it at its reported scale of up to 1,000 files and 50 receivers, with headers added at the same $h$. We will give it the same knowledge of updates and measure both load and delivery-time compute. Beating it means matching its load within 10% at 50 receivers. It also means growing the gap in our favor as user counts move into the hundreds, where the array families have known small $F$. For example, Michel–Wang report 3,003 sub-packets for 182 users, and Tang–Ramamoorthy report $1.07\times10^6$ against about $4.8\times10^{14}$ at $K=64$, $M/N=0.25$.
Two ablations isolate the key ingredients. The first fixes $F$ at the smallest value in the family and keeps the threshold policy. The second keeps the optimized $F$ but refreshes immediately on every update, which is pure push.
Why not just…?
Why not just use uncoded push/pull caching and skip coding entirely? Uncoded delivery loses the multicast gain. When users want distinct files, its peak load grows linearly in the number of users. The 1.7x–3x gains CA-CACM reports on dynamic content show that coded delivery remains valuable when files change. Our experiments sweep the number of users to locate the crossover. If the crossover lies above realistic user counts for small $F$, we will report that honestly.
Why not just re-place the whole cache every night and unicast whatever changes during the day? This is the real threat. If files rarely change within a peak period, nightly re-placement plus unicast bypass may be nearly optimal, and our machinery would add little. We will settle it by sweeping the ratio of update rate to the re-placement period. We will also use real change-time statistics from the MSMACRO crawl traces in Learning to Crawl, which cover 5,000 pages over 14 weeks, and identify the regime in which intra-period updates make sub-packet refresh pay off. If that regime is empty for realistic traces, the proposal's practical claim fails.
Why not just use CA-CACM's request-time graph coloring, which already tolerates updates? It does tolerate updates. However, it reacts only at delivery and has no way to shift refresh cost into off-peak time. Its coloring step also grows with the conflict graph, while array indexing is closed-form. The comparison above measures both load and compute, so the experiments can show whether the structured approach is worth its rigidity.
Proposed Experiments
We will use synthetic Zipf libraries with Poisson and Weibull request processes, matching the setups in Pedersen et al. and Deng–Dong. Updates will follow both Poisson sources and change times derived from MSMACRO. Edit locality $\rho$ will be swept from whole-file rewrites down to 1% patches. Each byte range will be mapped to a sub-packet index within the array, using either contiguous or interleaved layout.
The metrics are peak bytes, off-peak bytes, header fraction, served-version age, and delivery-time compute.
There are three decisive checks. First, the measured optimal $F$ should track $\sqrt{S/(\rho h)}$ within the array family, and its suboptimality gap should collapse when $\rho = 1$, since whole-file rewrites remove any reason for fine granularity. Second, the threshold policy should beat both pure push and pure lazy correction precisely where the off-peak/peak price ratio and the update-to-request ratio predict. Third, version-ledger delivery should produce zero decoding failures without loss, and should keep cost growth sublinear in the loss rate once acknowledgments are added.
References
- Optimal Push and Pull-Based Edge Caching for Dynamic Content
- On Coding for Cache-Aided Delivery of Dynamic Correlated Content
- Dynamic Coded Caching in Wireless Networks
- Placement Delivery Arrays From Combinations of Strong Edge Colorings
- Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes
- Dynamic Content Updates in Heterogeneous Wireless Networks
- Learning to Crawl