Stochastic coded caching with optimized shared-cache sizes and reduced subpacketization

This work studies the K-user broadcast channel with Λ caches, when the association between users and caches is random, i.e., for the scenario where each user can appear within the coverage area of – and subsequently is assisted by – a specific cache based on a given probability distribution. Caches are subject to a cumulative memory constraint that is equal to t times the size of the library. We provide a scheme that consists of three phases: the storage allocation phase, the content placement phase, and the delivery phase, and show that an optimized storage allocation across the caches together with a modified uncoded cache placement and delivery strategy alleviates the adverse effect of cache-load imbalance by significantly reducing the multiplicative performance deterioration due to randomness. In a nutshell, our work provides a scheme that manages to substantially mitigate the impact of cache-load imbalance in stochastic networks, as well as – compared to the best known state-of-the-art – the well-known subpacketization bottleneck by showing its applicability in deterministic settings for which it achieves the same delivery time – which was proven to be close to optimal for bounded values of t – with an exponential reduction in the subpacketization.