Cache-Aided Linear Function Computation
Abstract
We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the N sources stores its own independent file over a finite field and has an additional cache of normalized size M. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every N≥3, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for 0≤ M≤1/(2N−1) and M≥(N−1)/N, establishing the optimal memory--rate tradeoff in these two ranges.
Related
- Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast
- Finite-Resolution Microwave Linear Analog Computer (MiLAC)-Aided Multiuser Beamforming
- Efficient computation of mixture confidence sequences in generalized linear models
- Currently, there are no reasons to doubt the Riemann Hypothesis: The zeta function beyond the realm of computation
- Privacy-Constrained Function Computation in Distributed Databases
BibTeX
@misc{cai2026cacheaided,
title = {{Cache-Aided Linear Function Computation}},
author = {Xiaohong Cai and Ruze Zhang and Laigang Guo and Raymond W. Yeung},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20323},
eprint = {2610.20323},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20323},
}
RIS
TY - UNPB
TI - Cache-Aided Linear Function Computation
AU - Xiaohong Cai
AU - Ruze Zhang
AU - Laigang Guo
AU - Raymond W. Yeung
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20323
UR - https://arxiv.org/abs/2610.20323
AB - We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the N sources stores its own independent file over a finite field and has an additional cache of normalized size M. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every N≥3, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for 0≤ M≤1/(2N−1) and M≥(N−1)/N, establishing the optimal memory--rate tradeoff in these two ranges.
ER -