The Computational Complexity of Distributed Cache Placement

75 concepts65 papers1 proposal

In traditional computer science, caching is straightforward. If you have a single cache with uniform slots, a simple greedy strategy—like Belady’s optimal algorithm, which evicts the page needed furthest in the future—is perfectly optimal and runs in polynomial time. For decades, this predictable behavior formed the bedrock of memory management.

However, modern networks have shattered this simplicity. Today, content is distributed across a complex web of base stations, edge servers, and user devices with overlapping coverage areas. When we move from an isolated cache box to a distributed network, caching undergoes a fundamental mathematical shift: it transforms from a simple tracking problem into an NP-hard combinatorial optimization challenge.

The Breakdown of Uniformity

The first shift toward complexity happens when we modify the internal structure of the cache itself. In real-world systems, cache slots are rarely identical or unconstrained. Modern architectures often partition storage to guarantee fairness or handle multi-tier memory hierarchies.

As Marek Chrobak et al. demonstrate in Online Paging with Heterogeneous Cache Slots, simply introducing heterogeneous slots—where different slots incur different costs or performance characteristics—renders the offline optimal paging problem NP-hard. This means that even if you have perfect knowledge of every future file request, finding the absolute cheapest eviction schedule is computationally intractable.

Similarly, adding quality-of-service constraints complicates the math. When managing shared infrastructure, systems often enforce minimum storage guarantees, or "reserves," for individual users or applications. Manish Purohit et al. show in Efficient Caching with Reserves via Marking that these reserve constraints break classical eviction heuristics, turning a straightforward paging problem into an NP-hard task.

The Source of Complexity: Interdependent Utilities

Why does distributing caches across a network cause a combinatorial explosion? The root cause is interdependent utility.

In a single, isolated cache, the utility of caching File A is independent of whether File B is cached. In a distributed network, however, the value of caching an item at a specific node depends heavily on network topology, routing paths, and what is stored in neighboring caches.

Overlapping Service Areas

Consider a wireless small-cell network where a user can download data from multiple nearby base stations. If Base Station 1 caches a popular video, the marginal value of Base Station 2 caching that same video drops significantly. Conversely, if they coordinate, they can achieve massive efficiency gains.

In Multicast-aware Caching for Small Cell Networks, George Iosifidis et al. explain that when base stations synchronize their transmission windows to multicast shared files to multiple users simultaneously, the placement problem becomes intractable. The overlapping coverage and synchronized delivery mechanisms introduce tight dependencies that make finding a global optimum NP-hard.

Joint Routing and Placement

In a large network, content placement cannot be decoupled from request routing. A system must decide not only where to store a file, but also which path a user's request should take to fetch it.

As Mostafa Dehghan et al. prove in On the Complexity of Optimal Routing and Content Caching in Heterogeneous Networks, jointly optimizing routing and caching to minimize user delay is NP-complete. The complexity is driven by the topological structure of the network; evaluating every combination of user-to-cache paths alongside storage capacities creates an exponentially large search space.

Similarity Caching

In modern applications like recommendation engines or machine learning inference pipelines, a request does not always require an exact match. If a user requests an object, the system can satisfy that request using a "similar" cached object.

This flexibility introduces a new layer of interdependence. In Similarity Caching: Theory and Algorithms, Michele Garetto et al. show that because one cached item can satisfy multiple different types of nearby requests, the utility of any single item depends entirely on the presence of other similar items. This structural interdependence transforms cache state evaluation into an NP-hard combinatorial problem.

Exact Caching:
[Request: File A] ---> Is File A in Cache? ---> Yes (Hit) / No (Miss)
(Utility of File A is independent of File B)

Similarity Caching:
[Request: File A] ---> Is File A or something *similar* in Cache? 
(Utility of File A depends on whether similar items B or C are already covering the request space)

The Algebraic Complexity of Coded Delivery

The mathematical complexity deepens when networks move from caching whole files to coded caching. Instead of treating files as monolithic blocks, coded caching splits files into subfiles and uses algebraic operations (like XORing packets) to serve multiple distinct user requests simultaneously with a single broadcast.

While coded caching drastically reduces network traffic in theory, it introduces severe computational bottlenecks during the delivery phase. If content placement across user devices is non-uniform or arbitrary, finding the optimal combination of XORed packets becomes an index coding problem.

In An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching, Yi Ouyang 0002 et al. demonstrate that solving this delivery phase optimally is NP-hard, exhibiting double-exponential complexity for non-uniform scenarios. Even when trying to optimize multicast delivery across varying subfile sizes, the problem remains computationally intractable, as noted by the authors in Optimal Coded Multicast in Cache Networks with Arbitrary Content Placement.

Taming Intractability via Submodularity

Because finding exact solutions for large-scale distributed caching is computationally impossible (Milad Mahdian et al. in Kelly Cache Networks; Xi Peng et al. in Backhaul-Aware Caching Placement for Wireless Networks), network designers must rely on approximation algorithms.

Fortunately, many of these complex combinatorial formulations share a powerful mathematical property: submodularity.

Submodularity is the formal mathematical equivalent of "diminishing returns." If you add a file to an empty network of caches, the marginal benefit to the network is large. If you add that same file to a network that is already packed with content, the marginal benefit is much smaller.

$$\text{If } A \subseteq B, \text{ then } f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$$

When an optimization problem is submodular, a simple greedy algorithm—which iteratively places items in the location that yields the highest immediate marginal improvement—is guaranteed to find a near-optimal solution.

By shifting the focus from finding a perfect global optimum to proving submodular bounds, researchers can design practical, polynomial-time algorithms that keep massive, real-world content delivery networks efficient.

Key Foundational Work

Efficient and robust streaming provisioning in VPNs (2003) — contributed 3 concept elements to this direction.
Market sharing games applied to content distribution in ad-hoc networks (2004) — contributed 2 concept elements to this direction.
Optimal Time-Space Tradeoff in Probabilistic Inference (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_complexity_of_caching_4e164d7f,
  title = {computational complexity of caching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-caching/rdr_4e164d7f28d84028ba9bf3b040d36a62},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_caching_4e164d7f_v1,
  title = {computational complexity of caching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-caching/rdr_4e164d7f28d84028ba9bf3b040d36a62/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake