Coded Caching

The defining advantage of coded caching is the global caching gain, which is multiplicative and scales with the aggregate cache size across all users. Unlike uncoded caching where each user's cache only reduces their own demand, coded caching leverages the combined memory of the entire network. During the delivery phase, the server constructs a single coded multicast message that simultaneously serves multiple distinct requests. This gain is achieved through index coding principles, where the server XORs carefully selected file segments, allowing each user to decode their requested content by combining the transmission with their locally cached data.

The placement phase occurs during off-peak hours when network load is low. The server strategically populates each user's cache with carefully selected file fragments. In the canonical Maddah-Ali and Niesen scheme, placement is uncoded—each user stores a subset of bits from every file in the library without performing any computation. The key insight is that the placement must be designed with the delivery phase in mind, creating a specific pattern of overlapping cached content across users. This overlap is what enables the subsequent creation of coded multicast messages.

During peak demand, the server receives all user requests simultaneously and constructs a single coded transmission. The core mechanism relies on XOR operations in the finite field GF(2). The server identifies subsets of users where each user has cached the file requested by another user in the subset. It then transmits the XOR of the specific missing segments. Each user, possessing all but one component of the XOR, can recover their desired segment. This transforms multiple unicast transmissions into a single multicast, dramatically reducing the peak traffic load on the bottleneck link.

A fundamental trade-off in coded caching is the subpacketization level, which is the number of fragments each file must be split into. Achieving the optimal rate-memory trade-off requires exponential subpacketization in the number of users. For a system with K users, the file must be divided into a number of subpackets that grows combinatorially. This creates a practical bottleneck: while the theoretical gain is significant, the resulting file fragmentation increases implementation complexity, indexing overhead, and the size of the header required to identify each subpacket.

The decentralized variant removes the requirement for a coordinated placement phase where the server knows the exact number and identity of active users. Instead, each user independently populates its cache by randomly sampling bits from every file in the library according to a uniform distribution. During delivery, the server constructs coded messages based on the users currently present and their requests. This scheme achieves the same order-optimal rate as the centralized scheme while providing robustness to a dynamic user population, making it far more practical for real-world deployments with churn.

Coded caching defines a precise rate-memory trade-off that characterizes the fundamental limits of caching systems. The rate R(M) represents the minimum number of transmissions required in the delivery phase as a function of the cache size M. The optimal trade-off curve has two extreme points: - M=0: No caching, rate equals the number of distinct requests - M=N: Full caching of the entire library, rate is zero Between these extremes, coded caching achieves a rate that is strictly lower than uncoded caching. The exact characterization of this region for general networks remains an active area of information-theoretic research.

The mathematical foundation of coded caching. In an index coding problem, a server holds a set of messages, and each client possesses a subset of messages as side information. The goal is to satisfy all client demands with the minimum number of transmissions. Coded caching recasts the delivery phase as an index coding problem, where the clients' local caches act as side information, enabling a single multicast transmission to serve multiple distinct requests simultaneously.

Coded caching operates in two distinct phases:

• Placement Phase: Occurs during off-peak hours when network resources are abundant. The server fills each user's local cache with carefully designed file fragments according to a placement scheme. This phase is agnostic to future demands.
• Delivery Phase: Occurs during peak traffic. Users reveal their requests, and the server constructs and transmits coded multicast messages that simultaneously satisfy multiple users by leveraging the overlap between their cached content and requested files.

A multiplicative throughput improvement unique to coded caching. Unlike local caching gain, where each user benefits only from its own cache, global caching gain allows the network to serve multiple users with a single transmission. The gain scales with the total cache size across all users. For example, with K users and normalized cache size M, a coded delivery can achieve a rate reduction factor of up to 1 + K * M / N, where N is the total number of files.

The process of dividing each file into a large number of smaller fragments to create the combinatorial overlap required for coded delivery. The number of subpackets per file, denoted F, determines the granularity of the caching scheme. A fundamental trade-off exists: higher subpacketization enables greater coding gains but increases computational complexity and cache management overhead. Practical implementations seek schemes with low subpacketization while preserving near-optimal rate performance.

Two operational paradigms:

• Centralized Caching: The server coordinates cache contents across all users during placement, enabling precise combinatorial designs. Achieves optimal rate but requires global coordination.
• Decentralized Caching: Each user caches content independently without coordination. The Maddah-Ali-Niesen scheme operates in this mode, using random caching and coded delivery to still achieve significant global gains. More practical for large-scale, dynamic networks where coordination is infeasible.