bounds that improve over the state of the art.'
author:
- 'Qian Yu,  Mohammad Ali Maddah-Ali,  and A. Salman Avestimehr,  [^1] [^2] [^3] [^4] [^5] [^6]'
bibliography:
- 'UCache.bib'
title: 'Characterizing the Rate-Memory Tradeoff in Cache Networks within a Factor of 2'
---

Introduction
============

Caching is a common strategy to mitigate heavy peak-time communication load in a distributed network, via duplicating parts of the content in memories distributed across the network during off-peak times. In other words, caching allows us to trade distributed memory in the network for communication load reduction. Characterizing this fundamental *rate-memory tradeoff* is of great practical interest, and has been a research subject for several decades. For single-cache networks, the *rate-memory tradeoff* has been characterized for various scenarios in the 80s [@sleator1985amortized]. However, those techniques were found insufficient to tackle the multi-cache cases.

There has been a surge of recent results in information theory that aim at formalizing and characterizing such rate-memory tradeoff in multi-cache networks [@maddah-ali12a; @maddah-ali13; @pedarsani13; @niesen13; @ji2015order; @zhang15; @ji14b; @lim2016information; @bidokhti2016noisy; @zhang2015fundamental; @hachem14; @karamchandani14; @maddah2015cache; @naderializadeh2016fundamental; @7996347]. In particular, a basic bottleneck caching network was considered in [@maddah-ali12a], where a set of $K$ users is connected to a server through a 