Cache helps reduce communication for distributed linear computations
Cache-Aided Linear Function Computation
Information Theory
Summary
When many separate sources each hold different pieces of data, sometimes we want to combine their data in a specific way by adding and multiplying them. This study looks at how storing extra helpful bits in advance, before we know exactly what combination is needed, can save time communicating later. The authors found limits on how much communication can be saved and introduced a smart way to store extra data bits, which is best in some cases. Their method works well especially when the storage is very small or nearly full.
What this means in practice
- •For distributed system engineers: Design distributed data systems that minimize communication when computing functions by using pre-stored parity information at data sources.
- •For network protocol designers: Optimize communication protocols between data servers and clients by incorporating cache placement strategies to reduce data sent for linear function requests.
Authors
Xiaohong Cai, Ruze Zhang, Laigang Guo, Raymond W. Yeung
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\geq3$, 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\leq M\leq1/(2N-1)$ and $M\geq(N-1)/N$, establishing the optimal memory--rate tradeoff in these two ranges.