Hotplug coded caching improves data load under changing active users
Hotplug Coded Caching: Uncoded versus Row-Wise Coded Placements
Information Theory
Summary
The paper looks at how to store and deliver data efficiently when some users may suddenly be inactive. The authors find that simple uncoded storage causes extra delay when users go offline, while a more complex way called row-wise coded placement prevents extra delay but needs to know the total number of users. They also prove which ways of coding are best for certain numbers of files and users. This helps understand how to prepare data so that no matter who shows up, service stays fast.
What this means in practice
- •For network schedulers: Design cache strategies that maintain low data delivery load despite unpredictable user activity patterns.
- •For content delivery engineers: Implement coded caching schemes that optimize bandwidth when only subsets of users request content simultaneously.
Authors
Daniela Tuninetti
Abstract
In the hotplug coded caching model, $K$ users fill their caches of size $M$ as a function of $N$ files, but only an unknown subset of $A\leq K$ users is active in the delivery phase. In all regimes where the optimal hotplug tradeoff is known, it depends only on $A$, not on $K$; whether this holds in general is open. We show that: (i) Under uncoded placement, YMA delivery with MAN placement, where offline users are assigned the demands of active users, is optimal. Hence, offline users cause a strict load penalty at intermediate memory sizes, while the MAN placement is optimal for every number of active users; (ii) Under row-wise placement (RWP), where each cache is a function of the user's own row of each file, every classical scheme can be embedded in a Reed-Solomon code. The resulting hotplug scheme has the tradeoff of the classical model with $A$ users, for every $A\leq K$: there is no load penalty, but the placement depends on $K$. We then derive a converse for RWP, which shows that: (a) for $2\leq N\leq A$, the scheme of Gomez-Vilardebo (GV) is RWP optimal for $AM\leq N/(N-1)$, which settles the RWP tradeoff for $N=2$; (b) YMA is RWP optimal at $AM=N$; and (c) for $N=A=3$, GV is RWP optimal for $M\leq 1$. Hence, the Reed-Solomon embeddings of these schemes are optimal among embedded RWP schemes.