Decentralized coded caching attains order-optimal memory-rate tradeoff

By Mohammad Ali Maddah-Ali, Urs Niesen. Allerton Conference on Communication, Control, and Computing, 2013

627 citations recorded by the source corpus.

Replicating or caching popular content in memories distributed across the network is a technique to reduce peak network loads. Conventionally, the main performance gain of this caching was thought to result from making part of the requested data available closer to end users. Instead, we recently showed that a much more significant gain can be achieved by using caches to create multicasting opportunities, even for users with different demands, through coding across data streams. These simultaneous coded-multicasting opportunities are enabled by careful content overlap at the various caches in the network, created by a central coordinating server. In many scenarios, such a central coordinating server may not be available, raising the question if this multicasting gain can still be achieved in a more decentralized setting. In this paper, we propose an efficient caching scheme, in which the content placement is performed in a decentralized manner. In other words, no coordination is required for the content placement. Despite this lack of coordination, the proposed scheme is nevertheless able to create simultaneous coded-multicasting opportunities, and hence achieves a rate close to the centralized scheme.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/93c541ce1eb1ffbb77fd1cc8a2340b7f7c97a86a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Online Coded Caching (2013, methodology): “The delivery procedure is formall y similar to the delivery procedure of the decentralized caching algorithm in [18].”
Communication-Computation Efficient Gradient Coding (2018, background): “More recently, coding theory has found its way into distributed computing [9]–[24], following the path of exporting coding techniques to distributed storage [25], [26], caching [27] and queuing [28].”
Fundamental Limits of Caching (2012, methodology): “We have developed such a decentralized coded caching scheme in follow-up work [15] , in which each user caches a randomly selected subset of the bits.”
Coded caching with nonuniform demands (2013, methodology): “livers the requested ﬁles while maximally exploiting the side information available in each user’s cache. This is done by coding several requested ﬁles together. Algorithm 1 Coded caching scheme from [11] achieving peak rate (1) procedure PLACEMENT for k2K;n2Ndo User kcaches a random MF N -bit subse”
Coded MapReduce (2015, background): “1) Server 3 sends intermediate pairs (A, 11)[7], (A, 14)[8], (A, 10)[9], (A, 15)[10], (A, 15)[11], (A, 10)[12] and then (B, 21)[7], (B, 21)[8], (B, 21)[9], (B, 21)[10], (B, 21)[11], (B, 21)[12].”
Fundamental Limits of Caching in Wireless D2D Networks (2014, methodology): “Users u ∈ U make arbitrary requests f u ∈ F = { 1 , . . . , m , from a ﬁxed ﬁle library of size m .”
A Survey on Low Latency Towards 5G: RAN, Core Network and Caching Solutions (2017, methodology): “In most of these works [137], [138], [140], [142], [150], [153], [156], for a given scenario, an upper bound or lower bound for the considered metric is derived in order to get useful insights of this trade-off.”
Contract-Based Small-Cell Caching for Data Disseminations in Ultra-Dense Cellular Networks (2019, methodology): “Generally, the caching process consists of two stages: a data placement stage and a data delivery stage [6].”
Hierarchical coded caching (2014, methodology): “This single-layer setting was recently studied in [7], [8], where the authors proposed a coded caching scheme.”
Speeding Up Distributed Machine Learning Using Codes (2015, neutral): “Coded caching has been studied in many scenarios such as decentralized coded caching [67], online coded caching [68], hierarchical coded caching for wireless communication [69], and device-to-device coded caching [70].”