# The Optimal Rate Memory Tradeoff in Multi-Access Coded Caching: Large Cache Size

Vijith Kumar K. P., Brijesh Kumar Rai, Tony Jacob

► To cite this version:

Vijith Kumar K. P., Brijesh Kumar Rai, Tony Jacob. The Optimal Rate Memory Tradeoff in Multi-Access Coded Caching: Large Cache Size. ITW 2023 - IEEE Information Theory Workshop, Apr 2023, Saint-Malo, France. pp.165-169, 10.1109/ITW55543.2023.10161659. hal-04388612

HAL Id: hal-04388612

https://inria.hal.science/hal-04388612v1

Submitted on 11 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Optimal Rate Memory Tradeoff in Multi-Access Coded Caching: Large Cache Size

Vijith Kumar K P

Inria, France

Email: vijith-kumar.kizhakke-purakkal@inria.fr

Brijesh Kumar Rai

Ioncure Tech Private Limited

Email: brijesh.rai@gmail.com

Tony Jacob

IIT Guwahati, India

Email: tonyj@iitg.ac.in

**Abstract**—In this paper, we consider the (N, K, L) multi-access caching network where K users and K caches are connected to a server with N files, each of size F bits, through a shared error-free broadcast channel. Each user has access to L nearby caches, each of size MF bits, in a cyclic wrap-around manner. Even after several previous attempts, the exact characterization of the optimal rate memory tradeoff is still an open problem except in the case where L = K − 1 and L = 1 with large cache M ∈ [ N L · K − 1 K , N L ]. This paper determines the optimal rate memory tradeoff for the cache network with L = K − 2 and M ∈ [ N K − 2 · K − 1 K , N K − 2 ]. This is done by proposing a new caching scheme that operates at the memory rate pair ( N K − 2 · K − 1 K , 1 K ) and deriving a set of lower bounds to demonstrate the optimality of the scheme.

**Index Terms**—Coded caching, multi-access cache network, exact rate memory tradeoff.

<figure><img src="image_2.png" /><figcaption>Fig. 1. The (N, K, L) multi-access cache network</figcaption></figure>

## I. INTRODUCTION

In their seminal work [1], Maddah-Ali and Niesen introduced the concept of coded caching for the content distribution networks. They studied the (N, K, 1) canonical cache network, in which a server with N files, each of size F bits, is connected to the K users where each user has access to a dedicated cache of size MF bits, where M ∈ [0, N ]. This network operates in two phases. In the first phase, called the placement phase, the server populates each cache with functions of files stored in it without any prior knowledge about users’ future demands. When users reveal their demands, the server broadcasts a set of messages to help each user to obtain their requested file by using the cache contents it has access to. This phase is called the delivery phase. The main goal of the caching problem is to properly construct the placement phase so that the load experienced by the network during the delivery phase is minimal. The (N, K) canonical cache network formulated in [1] was extended to study several variants in [2]–[13].

In [10], Hachem et al. considered the (N, K, L) multi-access cache network, in which each user has access to L nearby caches, as illustrated in Fig.1. This network has a server with N files, {W₁, W₂, . . . , W_N}, each of size F bits, and is connected to K users, {U₁, U₂, . . . , U_K}, through an error-free broadcast channel. The network also has K caches, {Z₁, Z₂, . . . , Z_K}, each of size MF bits where M ∈ [0, N ]. Each user has access to L neighboring caches in a cyclic wrap around fashion. Each cache is also accessed by L users. Let d = [W_{d_1}, W_{d_2}, . . . , W_{d_K}] represent the users’ demand, with W_{d_l} representing the file requested by user U_l (here d_l

represent the file index). The server broadcasts a set of packets X_d of size R_d(M)F bits in response to the demand d to assist the user in computing their request using the cache contents it has access to. The amount R_d(M)F stands for the network load corresponding to the demand d, and the quantity R_d(M) stands for the rate corresponding to the demand d. If there is a caching scheme that allows each user to recover their requested file from the received packets of size at most R(M)F bits for a given cache size M, then the memory rate pair (M, R) is said to be achievable. The optimal rate memory tradeoff is defined as the minimum R that allows (M, R) to be achieved and it is denoted by:

$$R^*(M) = \min\{R \mid (M, R) \text{ is achievable}\} \quad (1)$$

The (N, K, L) cache network was extensively studied in [11]–[21]. In [11] proposed a caching scheme and derived a set of lower bounds on the achievable rate to demonstrate that the proposed scheme is optimal among uncoded caching schemes when L > K 2 . The lower bounds derived in [11] were further improved in [12]. For large cache, where M ∈ [ N L · K − 1 K , N L ], among all caching schemes, the schemes presented in [1] and [13] exactly characterizes the optimal rate memory tradeoff when L = 1 and L = K − 1, respectively. For the other values of L the exact nature of the optimal rate memory tradeoff is still an open problem. In this paper we address this issue partially by considering the cache network where each user has access to K − 2 nearby caches, i.e., L = K − 2. For this network we propose a new caching scheme which operates
<table><caption>TABLE I
CACHE CONTENTS PLACED IN STAGE 1 AND STAGE 2</caption><thead><tr><th>Cache</th><th>Stage 1</th><th>Stage 2</th></tr></thead><tbody><tr><td>Z<sub>1</sub></td><td>A<sub>(1,2)</sub>, A<sub>(1,3)</sub>, A<sub>(1,4)</sub>, B<sub>(1,2)</sub>, B<sub>(1,3)</sub>, B<sub>(1,4)</sub>,<br>C<sub>(1,2)</sub>, C<sub>(1,3)</sub>, C<sub>(1,4)</sub>, D<sub>(1,2)</sub>, D<sub>(1,3)</sub>, D<sub>(1,4)</sub>,<br>E<sub>(1,2)</sub>, E<sub>(1,3)</sub>, E<sub>(1,4)</sub></td><td>A<sub>(3,1)</sub> + A<sub>(4,1)</sub> + A<sub>(5,1)</sub>, B<sub>(3,1)</sub> + B<sub>(4,1)</sub> + B<sub>(5,1)</sub>,<br>C<sub>(3,1)</sub> + C<sub>(4,1)</sub> + C<sub>(5,1)</sub>, D<sub>(3,1)</sub> + D<sub>(4,1)</sub> + D<sub>(5,1)</sub>,<br>E<sub>(3,1)</sub> + E<sub>(4,1)</sub> + E<sub>(5,1)</sub></td></tr><tr><td>Z<sub>2</sub></td><td>A<sub>(2,3)</sub>, A<sub>(2,4)</sub>, A<sub>(2,5)</sub>, B<sub>(2,3)</sub>, B<sub>(2,4)</sub>, B<sub>(2,5)</sub>,<br>C<sub>(2,3)</sub>, C<sub>(2,4)</sub>, C<sub>(2,5)</sub>, D<sub>(2,3)</sub>, D<sub>(2,4)</sub>, D<sub>(2,5)</sub>,<br>E<sub>(2,3)</sub>, E<sub>(2,4)</sub>, E<sub>(2,5)</sub></td><td>A<sub>(4,2)</sub> + A<sub>(5,2)</sub> + A<sub>(1,2)</sub>, B<sub>(4,2)</sub> + B<sub>(5,2)</sub> + B<sub>(1,2)</sub>,<br>C<sub>(4,2)</sub> + C<sub>(5,2)</sub> + C<sub>(1,2)</sub>, D<sub>(4,2)</sub> + D<sub>(5,2)</sub> + D<sub>(1,2)</sub>,<br>E<sub>(4,2)</sub> + E<sub>(5,2)</sub> + E<sub>(1,2)</sub></td></tr><tr><td>Z<sub>3</sub></td><td>A<sub>(3,4)</sub>, A<sub>(3,5)</sub>, A<sub>(3,1)</sub>, B<sub>(3,4)</sub>, B<sub>(3,5)</sub>, B<sub>(3,1)</sub>,<br>C<sub>(3,4)</sub>, C<sub>(3,5)</sub>, C<sub>(3,1)</sub>, D<sub>(3,4)</sub>, D<sub>(3,5)</sub>, D<sub>(3,1)</sub>,<br>E<sub>(3,4)</sub>, E<sub>(3,5)</sub>, E<sub>(3,1)</sub></td><td>A<sub>(5,3)</sub> + A<sub>(1,3)</sub> + A<sub>(2,3)</sub>, B<sub>(5,3)</sub> + B<sub>(1,3)</sub> + B<sub>(2,3)</sub>,<br>C<sub>(5,3)</sub> + C<sub>(1,3)</sub> + C<sub>(2,3)</sub>, D<sub>(5,3)</sub> + D<sub>(1,3)</sub> + D<sub>(2,3)</sub>,<br>E<sub>(5,3)</sub> + E<sub>(1,3)</sub> + E<sub>(2,3)</sub></td></tr><tr><td>Z<sub>4</sub></td><td>A<sub>(4,5)</sub>, A<sub>(4,1)</sub>, A<sub>(4,2)</sub>, B<sub>(4,5)</sub>, B<sub>(4,1)</sub>, B<sub>(4,2)</sub>,<br>C<sub>(4,5)</sub>, C<sub>(4,1)</sub>, C<sub>(4,2)</sub>, D<sub>(4,5)</sub>, D<sub>(4,1)</sub>, D<sub>(4,2)</sub>,<br>E<sub>(4,5)</sub>, E<sub>(4,1)</sub>, E<sub>(4,2)</sub></td><td>A<sub>(1,4)</sub> + A<sub>(2,4)</sub> + A<sub>(3,4)</sub>, B<sub>(1,4)</sub> + B<sub>(2,4)</sub> + B<sub>(3,4)</sub>,<br>C<sub>(1,4)</sub> + C<sub>(2,4)</sub> + C<sub>(3,4)</sub>, D<sub>(1,4)</sub> + D<sub>(2,4)</sub> + D<sub>(3,4)</sub>,<br>E<sub>(1,4)</sub> + E<sub>(2,4)</sub> + E<sub>(3,4)</sub></td></tr><tr><td>Z<sub>5</sub></td><td>A<sub>(5,1)</sub>, A<sub>(5,2)</sub>, A<sub>(5,3)</sub>, B<sub>(5,1)</sub>, B<sub>(5,2)</sub>, B<sub>(5,3)</sub>,<br>C<sub>(5,1)</sub>, C<sub>(5,2)</sub>, C<sub>(5,3)</sub>, D<sub>(5,1)</sub>, D<sub>(5,2)</sub>, D<sub>(5,3)</sub>,<br>E<sub>(5,1)</sub>, E<sub>(5,2)</sub>, E<sub>(5,3)</sub></td><td>A<sub>(2,5)</sub> + A<sub>(3,5)</sub> + A<sub>(4,5)</sub>, B<sub>(2,5)</sub> + B<sub>(3,5)</sub> + B<sub>(4,5)</sub>,<br>C<sub>(2,5)</sub> + C<sub>(3,5)</sub> + C<sub>(4,5)</sub>, D<sub>(2,5)</sub> + D<sub>(3,5)</sub> + D<sub>(4,5)</sub>,<br>E<sub>(2,5)</sub> + E<sub>(3,5)</sub> + E<sub>(4,5)</sub></td></tr></tbody></table>

at the memory rate pair $(\frac{N}{K-2} \cdot \frac{K-1}{K}, \frac{1}{K})$. We also demonstrate the optimality of the scheme by deriving a set of lower bounds.

The rest of this paper is structured as follows. In Section II, we present some key identities and notations that will be used throughout this paper. We consider the (5, 5, 3) multi-access cache network in Section III and present the caching scheme. In Section IV, we generalize this scheme for the $(N, K, K-2)$ multi-access cache network to obtain an exact characterization of the optimal rate memory tradeoff when $M \in [\frac{N}{K-2} \cdot \frac{K-1}{K-2}, \frac{N}{K-2}]$. We conclude the paper in Section V.

## II. PRELIMINARY RESULTS

In this section we present some preliminary results and notations which are used repeatedly in the paper. We use $[L]$ to represent the set $\{1, 2, \dots, L\}$, $Z_{[L]}$ to represent the set $\{Z_1, Z_2, \dots, Z_L\}$, and $W_{[L]}$ to represent the set $\{W_1, W_2, \dots, W_L\}$. For integers $J$ and $I$,

$$<J>_I = \begin{cases} J \bmod I & \text{if } J \bmod I \neq 0 \\ I & \text{if } J \bmod I = 0 \end{cases}$$

Let $\mathbf{P}$ be a set, then $<\mathbf{P}>_I$ is defined as

$$<\mathbf{P}>_I = \{<l>_I : l \in \mathbf{P}\}$$

For integers $K, l, m$, consider the set $S_{(l,m)}^K$ is defined as

$$S_{(l,m)}^K = [K] \setminus \{<l, l-1, \dots, l-m+1>\}_K$$

This set has the following property

$$S_{(l,m+p)}^K = S_{(l,m)}^K \setminus \{<l-m, \dots, l-m-p+1>\}_K$$

Let $Z_i$ denote the set of cache accessed by user $U_i$

$$Z_i = \{Z_i, Z_{<i+1>_K}, \dots, Z_{<i+L-1>_K}\} \quad (2)$$

For the $(N, K, L)$ cache network with cache size $M$, the memory rate pair $(M, R)$ is said to be achievable if there is a scheme with $R(M) \le R$. For a such a scheme, we have

$$H(Z_l) \le M \quad (3)$$

$$H(X_d) \le R \quad (4)$$

$$H(Z_l, X_d) = H(W_{d_l}, Z_l, X_d) \quad (5)$$

$$H(W_1, \dots, W_N, Z_l, X_d) = H(W_1, \dots, W_N), \quad (6)$$

where (3) follows from the fact that size of each cache is $M$, (4) follows from the fact that for any demand $d$, the size of $X_d$ is at most $R(M) \le R$, (5) follows from the fact that the file $W_{d_l}$ can be computed from $X_d$ and $Z_l$, and (6) follows from the fact that $Z_l$ and $X_d$ are functions of files $W_{[N]}$.

## III. THE (5, 5, 3) MULTI-ACCESS CACHE NETWORK

Consider the (5, 5, 3) multi-access cache network, which consists of a server with five files, $A, B, C, D$, and $E$, each of size $F$ bits, and five users, $U_1, U_2, U_3, U_4$ and $U_5$. The network has five caches, each of $\frac{4}{3}F$ bits in size: $Z_1, Z_2, Z_3, Z_4$, and $Z_5$. Three nearby caches are accessible to each user. User 1 has access to caches $Z_1, Z_2$, and $Z_3$, user 2 has access to caches $Z_2, Z_3$, and $Z_4$, user 3 has access to caches $Z_3, Z_4$, and $Z_5$, user 4 has access to caches $Z_4, Z_5$, and $Z_1$, and user 5 has access to caches $Z_5, Z_1$, and $Z_2$. Each cache is accessed by three users. During the placement phase the server splits each file into 15 non-overlapping subfiles, each of size $\frac{1}{15}F$ bits. The subfiles are:

<table><thead><tr><th>File</th><th>Subfiles</th></tr></thead><tbody><tr><td>A</td><td>A<sub>(1,2)</sub>, A<sub>(1,3)</sub>, A<sub>(1,4)</sub>, A<sub>(2,3)</sub>, A<sub>(2,4)</sub>, A<sub>(2,5)</sub>, A<sub>(3,4)</sub>,<br>A<sub>(3,5)</sub>, A<sub>(3,1)</sub>, A<sub>(4,5)</sub>, A<sub>(4,1)</sub>, A<sub>(4,2)</sub>, A<sub>(5,1)</sub>, A<sub>(5,2)</sub>, A<sub>(5,3)</sub></td></tr><tr><td>B</td><td>B<sub>(1,2)</sub>, B<sub>(1,3)</sub>, B<sub>(1,4)</sub>, B<sub>(2,3)</sub>, B<sub>(2,4)</sub>, B<sub>(2,5)</sub>, B<sub>(3,4)</sub>,<br>B<sub>(3,5)</sub>, B<sub>(3,1)</sub>, B<sub>(4,5)</sub>, B<sub>(4,1)</sub>, B<sub>(4,2)</sub>, B<sub>(5,1)</sub>, B<sub>(5,2)</sub>, B<sub>(5,3)</sub></td></tr><tr><td>C</td><td>C<sub>(1,2)</sub>, C<sub>(1,3)</sub>, C<sub>(1,4)</sub>, C<sub>(2,3)</sub>, C<sub>(2,4)</sub>, C<sub>(2,5)</sub>, C<sub>(3,4)</sub>,<br>C<sub>(3,5)</sub>, C<sub>(3,1)</sub>, C<sub>(4,5)</sub>, C<sub>(4,1)</sub>, C<sub>(4,2)</sub>, C<sub>(5,1)</sub>, C<sub>(5,2)</sub>, C<sub>(5,3)</sub></td></tr><tr><td>D</td><td>D<sub>(1,2)</sub>, D<sub>(1,3)</sub>, D<sub>(1,4)</sub>, D<sub>(2,3)</sub>, D<sub>(2,4)</sub>, D<sub>(2,5)</sub>, D<sub>(3,4)</sub>,<br>D<sub>(3,5)</sub>, D<sub>(3,1)</sub>, D<sub>(4,5)</sub>, D<sub>(4,1)</sub>, D<sub>(4,2)</sub>, D<sub>(5,1)</sub>, D<sub>(5,2)</sub>, D<sub>(5,3)</sub></td></tr><tr><td>E</td><td>E<sub>(1,2)</sub>, E<sub>(1,3)</sub>, E<sub>(1,4)</sub>, E<sub>(2,3)</sub>, E<sub>(2,4)</sub>, E<sub>(2,5)</sub>, E<sub>(3,4)</sub>,<br>E<sub>(3,5)</sub>, E<sub>(3,1)</sub>, E<sub>(4,5)</sub>, E<sub>(4,1)</sub>, E<sub>(4,2)</sub>, E<sub>(5,1)</sub>, E<sub>(5,2)</sub>, E<sub>(5,3)</sub></td></tr></tbody></table>
<table><caption>TABLE II
FILE RECOVERY</caption><thead><tr><th colspan="2">Cache Contents</th><th>Received Packets</th><th>Computed Subfile</th></tr></thead><tbody><tr><td>Uncoded</td><td>Coded</td><td></td><td></td></tr><tr><td>P<sub>(2,5)</sub>, P<sub>(3,5)</sub><br/>T<sub>(1,4)</sub>, T<sub>(2,4)</sub>, T<sub>(3,4)</sub></td><td>Q<sub>(3,1)</sub> + Q<sub>(4,1)</sub> + Q<sub>(5,1)</sub><br/>R<sub>(4,2)</sub> + R<sub>(5,2)</sub> + R<sub>(1,2)</sub><br/>S<sub>(5,3)</sub> + S<sub>(1,3)</sub> + S<sub>(2,3)</sub></td><td>P<sub>(2,5)</sub> + P<sub>(3,5)</sub> + P<sub>(4,5)</sub> + Q<sub>(3,1)</sub> + Q<sub>(4,1)</sub> + Q<sub>(5,1)</sub><br/>+ R<sub>(4,2)</sub> + R<sub>(5,2)</sub> + R<sub>(1,2)</sub> + S<sub>(5,3)</sub> + S<sub>(1,3)</sub> + S<sub>(2,3)</sub><br/>+ T<sub>(1,4)</sub> + T<sub>(2,4)</sub> + T<sub>(3,4)</sub></td><td>P<sub>(4,5)</sub></td></tr><tr><td>P<sub>(3,1)</sub>, Q<sub>(1,2)</sub>, R<sub>(2,3)</sub><br/>S<sub>(1,4)</sub>, S<sub>(2,4)</sub>, T<sub>(2,5)</sub>, T<sub>(3,5)</sub></td><td>Q<sub>(4,2)</sub> + Q<sub>(5,2)</sub> + Q<sub>(1,2)</sub><br/>R<sub>(5,3)</sub> + R<sub>(1,3)</sub> + R<sub>(2,3)</sub></td><td>P<sub>(3,1)</sub> + P<sub>(4,1)</sub> + Q<sub>(4,2)</sub> + Q<sub>(5,2)</sub> + R<sub>(5,3)</sub> + R<sub>(1,3)</sub><br/>+ S<sub>(1,4)</sub> + S<sub>(2,4)</sub> + T<sub>(2,5)</sub> + T<sub>(3,5)</sub></td><td>P<sub>(4,1)</sub></td></tr><tr><td>Q<sub>(1,3)</sub>, Q<sub>(2,3)</sub>, R<sub>(1,4)</sub>, S<sub>(2,5)</sub>, T<sub>(3,1)</sub></td><td>Q<sub>(5,3)</sub> + Q<sub>(1,3)</sub> + Q<sub>(2,3)</sub></td><td>P<sub>(4,2)</sub> + Q<sub>(5,3)</sub> + R<sub>(1,4)</sub> + S<sub>(2,5)</sub> + T<sub>(3,1)</sub></td><td>P<sub>(4,2)</sub></td></tr></tbody></table>

We have chosen the notation $W_{(i,j)}$ to represent the subfiles to simplify further explanations. There are two stages to the placement phase. The server copies 15 uncoded subfiles during the first stage of the placement phase. During the second stage of the placement phase, the server copies 5 functions of subfiles. TABLE I shows the cache contents for each user after the placement phase. It can be noted that during the placement phase the server copies 20 packets, each of size $\frac{1}{15}F$ bits, into each cache. These packets collectively occupies the space of $\frac{4}{3}F$ bits.

Consider a demand $d = [P, Q, R, S, T]$, where $P, Q, R, S, T \in \{A, B, C, D, E\}$. In this demand, $P$ represents the file requested by user 1, $Q$ represents the file requested by user 2, $R$ represents the file requested by user 3, $S$ represents the file requested by user 4, and $T$ represents the file requested by user 5. In response to the demand $d$ the server broadcasts a set of packets:

$$X_d = \left\{ \begin{array}{l} P_{(2,5)} + P_{(3,5)} + P_{(4,5)} + Q_{(3,1)} + Q_{(4,1)} + Q_{(5,1)} \\ + R_{(4,2)} + R_{(5,2)} + R_{(1,2)} + S_{(5,3)} + S_{(1,3)} + S_{(2,3)} \\ + T_{(1,4)} + T_{(2,4)} + T_{(3,4)} \\ P_{(3,1)} + P_{(4,1)} + Q_{(4,2)} + Q_{(5,2)} + R_{(5,3)} + R_{(1,3)} \\ + S_{(1,4)} + S_{(2,4)} + T_{(2,5)} + T_{(3,5)} \\ P_{(4,2)} + Q_{(5,3)} + R_{(1,4)} + S_{(2,5)} + T_{(3,1)} \end{array} \right\}$$

It can be noted that the broadcast message consists of three packets each of size $\frac{1}{15}F$ bits. Thus, the load corresponding to the demand $d$ is

$$3 \times \frac{1}{15} F = \frac{1}{5} F \text{ bits}$$

and the corresponding rate is $R = \frac{1}{5}$.

Consider user 1 in order to better understand how each user recovers the requested file from the received packets $X_d$ using the cache contents it has access to. User 1 has access to the caches $Z_1, Z_2$, and $Z_3$. Thus, the subfiles $P_{(1,2)}, P_{(1,3)}, P_{(1,4)}, P_{(2,3)}, P_{(2,4)}, P_{(2,5)}, P_{(3,4)}, P_{(3,5)}$, and $P_{(3,1)}$ are accessible to user 1, but in order to compute the file $P$, it needs the subfiles $P_{(4,5)}, P_{(4,1)}, P_{(4,2)}, P_{(5,1)}, P_{(5,2)}$, and $P_{(5,3)}$. With the use of the cached packets, the user computes the subfiles $P_{(4,5)}, P_{(4,1)}$, and $P_{(4,2)}$ from the received packets, as shown in TABLE II. Once the user obtains the subfile $P_{(4,1)}$, combining this subfile with the cached packets $P_{(3,1)}$ and $P_{(3,1)} + P_{(4,1)} + P_{(5,1)}$, the user computes the subfile

$P_{(5,1)}$. Similarly, by combining the subfile $P_{(4,2)}$ with the cache contents $P_{(1,2)}$ and $P_{(4,2)} + P_{(5,2)} + P_{(1,2)}$, the user computes the subfile $P_{(5,2)}$. The user computes the remaining subfile, $P_{(5,3)}$, by combining the caches subfiles $P_{(1,3)}$ and $P_{(2,3)}$ with the cached packet $P_{(5,3)} + P_{(1,3)} + P_{(2,3)}$. In a similar fashion, other users compute their requested files. We summarise as:

**Lemma 1.** The memory rate pair $(\frac{4}{3}, \frac{1}{5})$ is achievable for the $(5, 5, 3)$ multi-access cache network.

For large cache size, where $M \in [\frac{4}{3}, \frac{5}{3}]$, all memory rate pairs $(M, \frac{1}{5} - \frac{3}{5}(M - \frac{4}{3}))$ can be achieved by memory sharing the proposed scheme and the scheme proposed in [13] that achieves the memory rate pair $(\frac{5}{3}, 0)$, where all files are available in the caches. We have a matching lower bound using cut-set arguments:

**Lemma 2.** For the $(5, 5, 3)$ multi-access cache network, the achievable memory rate pair $(M, R)$ must satisfy the constraint

$$3M + 5R \geq 5$$

*Proof.* Here, we provide proof of the lemma for the purpose of completeness. Let $X_1^p$ represent a set of packets broadcast in response to a demand, where user 1 request for file $p \in \{A, B, C, D, E\}$. We have

$$\begin{align*} 3M + 5R &\geq H(Z_1) + H(Z_2) + H(Z_3) + H(X_1^A) \\ &\quad + H(X_1^B) + H(X_1^C) + H(X_1^D) + H(X_1^E) \\ &\stackrel{(a)}{\geq} H(Z_1, Z_2, Z_3, X_1^A, X_1^B, X_1^C, X_1^D, X_1^E) \\ &\stackrel{(b)}{\geq} H(Z_1, X_1^A, X_1^B, X_1^C, X_1^D, X_1^E) \\ &\stackrel{(c)}{=} H(A, B, C, D, E, Z_1, X_1^A, X_1^B, X_1^C, X_1^D, X_1^E) \\ &\stackrel{(d)}{=} H(A, B, C, D, E) = 5 \end{align*}$$

where (a) follows from sub-modularity property of entropy, (b) follows from (2), (c) follows from (5), and (d) follows from (6). $\square$

We summarise as:
<table><caption>TABLE III
FILE RECOVERY</caption><thead><tr><th colspan="2">Constraints</th><th colspan="2">Cache Contents</th><th>Compute Packet</th></tr><tr><th colspan="2"></th><th>Uncoded</th><th>Coded</th><th></th></tr></thead><tbody><tr><td rowspan="2">1 ≤ j ≤ K − p − 2</td><td>p = 0</td><td>−</td><td rowspan="2">q ∈ s<sup>K</sup><sub>(i+j+p-1>K)</sub> &sum; W<sub>d<sub>i+j</sub>,(q,&lt;i+j+p-1&gt;<sub>K</sub>)</sub></td><td rowspan="2">q ∈ s<sup>K</sup><sub>(i+j+p,2)</sub> &sum; W<sub>d<sub>i+j</sub>,(q,&lt;i+j+p-1&gt;<sub>K</sub>)</sub></td></tr><tr><td>p ≠ 0</td><td>W<sub>d<sub>i+j</sub>,(q,&lt;i+j+p-1&gt;<sub>K</sub>)</sub>, where q ∈ {i + j − 1, ..., i + j + p − 2} &gt;<sub>K</sub></td></tr><tr><td>K − p − 1 ≤ j ≤ K − 1</td><td></td><td>W<sub>d<sub>i+j</sub>,(q,&lt;i+j+p-1&gt;<sub>K</sub>)</sub>, where q ∈ s<sup>K</sup><sub>(i+j+p,2)</sub></td><td></td><td></td></tr></tbody></table>

**Theorem 1.** For the (5, 5, 3) multi-access cache network, the optimal rate memory tradeoff, when $M \in [\frac{4}{3}, \frac{5}{3}]$, is given by

$$R = 1 - \frac{3}{5}M.$$

The above theorem is a special case of Theorem 3.

#### IV. NEW CACHING SCHEME

In this section we extend the caching scheme to the $(N, K, K-2)$ cache network to achieve the memory rate pair $(\frac{N}{K-2}, \frac{K-1}{K}, \frac{1}{K})$. Then we derive a matching lower bound to demonstrate the proposed scheme is optimal.

##### A. Placement phase

During the placement phase, the server split each file into $K(K-2)$ subfiles, each of size $\frac{1}{K(K-2)}F$ bits. The subfiles of file $W_n$ are:

$$W_{n,(i,j)} \text{ where } i \in [K] \text{ and } j \in S_{(i,2)}^K$$

The placement phase takes place in two stages. In the first stage, the server copies the uncoded subfiles $W_{n,(i,j)}$, for all $n \in [N]$ and $j \in S_{(i,2)}^K$, into cache $Z_i$. In the second stage, the server copies several functions of the subfiles into each cache resulting in the cache $Z_i$ having the contents:

<table><thead><tr><th>Stage</th><th>Cached packet</th><th>Constraint</th><th>Number</th></tr></thead><tbody><tr><td>Stage 1</td><td>$W_{n,(i,j)}$</td><td>$n \in [N]$ and $j \in S_{(i,2)}^K$</td><td>$N(K-2)$</td></tr><tr><td>stage 2</td><td>$\sum_{l \in S_{(i+1,2)}^K} W_{n,(l,i)}$</td><td>$n \in [N]$</td><td>$N$</td></tr></tbody></table>

It can be noted that the subfiles $W_{n,(i,j)}$, for all $n \in [N]$ and $j \in S_{(i,2)}^K$, are available at cache $Z_i$ in uncoded form and the subfiles $W_{n,(l,i)}$, for all $n \in [N]$ and $l \in S_{(i+1,2)}^K$, are available at cache $Z_i$ in coded form. The total number of packets, each of size $\frac{1}{K(K-2)}F$ bits, copied in each cache is

$$N(K-2) + N = N(K-1)$$

and these subfiles occupies the space of $\frac{N}{(K-2)} \cdot \frac{K-1}{K}F$ bits.

##### B. Delivery phase

Let the server receive a demand **d**, where each user reveals their demand. During the delivery phase the server broadcasts a set of packets:

$$X_d = \bigcup_{p=0}^{K-3} \sum_{m \in [K]} \left[ \sum_{q \in S_{(m+p,p+2)}^K} W_{d_m,(q,<m+p-1>K)} \right]$$

In response to demand **d**, the server broadcasts $K-2$ packets, each of size $\frac{1}{K(K-2)}F$ bits. Thus, the rate corresponding to the demand **d** is:

$$R = (K-2) \times \frac{1}{K(K-2)} = \frac{1}{K}$$

##### C. File recovery

To understand how each user computes its requested file from the received packet $X_d$ with the help of the cache contents it has access to, consider user $U_k$ who requests the file $W_{d_k}$. The user has access to the set of caches

$$\mathcal{Z}_k = \{Z_u : u \in S_{(k-1,2)}^K\}$$

As a result, the user has access to the subfiles $W_{d_k,(i,j)}$, where $i \in S_{(k-1,2)}^K$ and $j \in S_{(i,2)}^K$. The user also has access to the subfiles $W_{n,(i,j)}$, where $n \in [N]$, $i \in S_{(k-1,2)}^K$ and $j \in S_{(i,2)}^K$. The user needs the subfiles $W_{d_k,(r,s)}$, where $r \in \{<k-2, k-1]\} &gt;_K$ and $s \in S_{(r,2)}^K$, to compute file $W_{d_k}$, and the user recovers these subfiles in two stages. In the first stage, the user computes the subfile $W_{d_k,(k-2,s)}$, where $s \in S_{(k-2,2)}^K$. For $0 \le p \le K-3$ and $1 \le j \le K-1$, the user computes the packet

$$\sum_{q \in S_{(k+j+p, p+2)}^K} W_{d_{k+j}, (q, <k+j+p-1>K)}, \quad (7)$$

by combining the cached packets available to it, as shown in TABLE III. Consider the received packet

$$\sum_{m \in [K]} \left[ \sum_{q \in S_{(m+p, p+2)}^K} W_{d_m, (q, <m+p-1>K)} \right] \quad (8)$$

where $0 \le p \le K-3$. Let $m = <k + j >_K$ where $0 \le j \le K-1$. By combining (7) and (8), the user computes the packet

$$\sum_{q \in S_{(k+p, p+2)}^K} W_{d_i, (q, <k+p-1>K)}. \quad (9)$$

From (9), the user computes the subfile $W_{d_k, (<k-2>K, <k+p-1>K>)}$ with the aid of the caches subfiles $W_{d_k, (q, <k+p-1>K>)}$, where $q \in S_{(k+p,p+3)}^K$. Now the user has the subfiles

$$W_{d_k, (q, r)} \quad (10)$$
where $q \in [K] \setminus \{k-1\}$ and $r \in S_{(q,2)}^K$. Now the user needs the subfiles $W_{d_k,(k-1,l)}$, where $l \in S_{(k-1,2)}^K$, which are available to the user in coded form

$$ \sum_{t \in S_{(l+1,2)}^K} W_{d_k,(t,l)} \quad (11) $$

for $l \in S_{(k-1,2)}^K$. The user computes the subfiles $W_{d_k,(k-1,l)}$ by combining (10) and (11). Using all the recovered subfiles the user can reconstruct the requested file $W_{d_k}$. These observations can be summarized as:

**Theorem 2.** The memory rate pair $(\frac{N}{K-2}, \frac{K-1}{K}, \frac{1}{K})$ is achievable for the $(N, K, K-2)$ multi-access cache network.

### D. Matching lower bound

We derive a matching lower bound in the following theorem:

**Theorem 3.** For the $(N, K, K-2)$ multi-access cache network, the achievable memory rate pair $(M, R)$ must satisfy the constraint

$$ (K-2)M + NR \geq N $$

*Proof.* Let $X_1^p$ represent a set of packets broadcast in response to a demand where user 1 request for file $W_p \in W_{[N]}$. Let $X_1^{[N]} = \{X_1^1, X_1^2, \dots, X_1^N\}$. Now we have

$$ \begin{align*} (K-2)M + NR &\geq H(Z_{[K-2]}) + H(X_1^{[N]}) \\ &\stackrel{(a)}{\geq} H(Z_{[K-2]}, X_1^{[N]}) \\ &\stackrel{(b)}{=} H(Z_1, X_1^{[N]}) \\ &\stackrel{(c)}{=} H(W_{[N]}, Z_1, X_1^{[N]}) \\ &\stackrel{(d)}{=} H(W_{[N]}) = N \end{align*} $$

where (a) follows from sub-modularity property of entropy, (b) follows from (2), (c) follows from (5), and (d) follows from (6). □

We summarise as:

**Theorem 4.** For the $(N, K, K-2)$ multi-access cache network, the optimal rate memory tradeoff, when $M \in [\frac{N}{K-2}, \frac{K-1}{K}, \frac{N}{K-2}]$, is given by

$$ R = 1 - \frac{(K-2)}{N} M. $$

For large cache size, where $M \in [\frac{N}{K-2}, \frac{K-1}{K}, \frac{N}{K-2}]$, all memory rate pairs $(M, \frac{1}{K} - \frac{K-2}{N}(M - \frac{N}{K-2} \frac{K-1}{K}))$ can be achieved by memory sharing the proposed scheme and the scheme proposed in [13] that achieves the memory rate pair $(\frac{N}{K-2}, 0)$.

## V. CONCLUSIONS

In this paper, we considered the $(5, 5, 3)$ multi-access cache network where each user has access to 3 nearby caches. For this network, we proposed a new caching scheme that operates at the memory rate pair $(\frac{4}{3}, \frac{1}{5})$, and also derived a lower bound, demonstrating the proposed scheme's optimality. We extended

this scheme and the lower bound derivation for the $(N, K, K-2)$ multi-access cache network. This proved the optimality of the proposed scheme and lead to a characterization of the exact rate memory tradeoff for the multi-access cache network for large cache size.

## ACKNOWLEDGEMENTS

This research was supported in part by the French Government through the “Plan de Relance” and “Programme d’investissements d’avenir”.

## REFERENCES

[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” *IEEE Transactions on Information Theory*, vol. 60, no. 5, pp. 2856–2867, 2014.

[2] —, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” *IEEE/ACM Transactions on Networking*, vol. 23, no. 4, pp. 1029–1040, 2015.

[3] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform demands,” *IEEE Transactions on Information Theory*, vol. 63, no. 2, pp. 1146–1158, 2017.

[4] N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. N. Diggavi, “Hierarchical coded caching,” *IEEE Transactions on Information Theory*, vol. 62, no. 6, pp. 3212–3229, 2016.

[5] S. P. Shariatpanahi, S. A. Motahari, and B. H. Khalaj, “Multi-server coded caching,” *IEEE Transactions on Information Theory*, vol. 62, no. 12, pp. 7253–7271, 2016.

[6] E. Parrinello and P. Elia, “Coded caching with optimized shared-cache sizes,” in *2019 IEEE Information Theory Workshop (ITW)*. IEEE, 2019, pp. 1–5.

[7] A. Malik, B. Serbetci, E. Parrinello, and P. Elia, “Fundamental limits of stochastic caching networks,” *arXiv preprint arXiv:2005.13847*, 2020.

[8] Ç. Yavar, K. Wan, R. F. Schaefer, and G. Caire, “On the optimality of d2d coded caching with uncoded cache placement and one-shot delivery,” *IEEE Transactions on Communications*, vol. 67, no. 12, pp. 8179–8192, 2019.

[9] K. Wan, D. Tuninetti, M. Ji, G. Caire, and P. Piantanida, “Fundamental limits of decentralized data shuffling,” *IEEE Transactions on Information Theory*, vol. 66, no. 6, pp. 3616–3637, 2020.

[10] J. Hachem, N. Karamchandani, and S. N. Diggavi, “Coded caching for multi-level popularity and access,” *IEEE Transactions on Information Theory*, vol. 63, no. 5, pp. 3108–3141, 2017.

[11] K. S. Reddy and N. Karamchandani, “Rate-memory trade-off for multi-access coded caching with uncoded placement,” *IEEE Transactions on Communications*, 2020.

[12] K. Krishnan Namboodiri and B. Sundar Rajan, “An improved lower bound for multi-access coded caching,” *arXiv e-prints*, pp. arXiv:2201.2022.

[13] S. Sasi and B. S. Rajan, “An improved multi-access coded caching with uncoded placement,” *arXiv preprint arXiv:2009.05377*, 2020.

[14] E. Peter and B. S. Rajan, “Coded caching with shared caches from generalized placement delivery arrays,” in *2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)*. IEEE, 2021, pp. 380–386.

[15] E. Parrinello, A. Unsal, and P. Elia, “Fundamental limits of caching in heterogeneous networks with uncoded prefetching,” *arXiv preprint arXiv:1811.06247*, 2018.

[16] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Coded caching for heterogeneous systems: An optimization perspective,” *IEEE Transactions on Communications*, vol. 67, no. 8, pp. 5321–5335, 2019.

[17] M. Dutta and A. Thomas, “Decentralized coded caching for shared caches,” *IEEE Communications Letters*, vol. 25, no. 5, pp. 1458–1462, 2021.

[18] F. Brunero and P. Elia, “Fundamental limits of combinatorial multi-access caching,” *arXiv preprint arXiv:2110.07426*, 2021.

[19] A. Malik, B. Serbetci, E. Parrinello, and P. Elia, “Fundamental limits of stochastic shared-cache networks,” *IEEE Transactions on Communications*, vol. 69, no. 7, pp. 4433–4447, 2021.

[20] P. N. Muralidhar, D. Katyal, and B. S. Rajan, “Maddah-Ali-Niesen scheme for multi-access coded caching,” in *2021 IEEE Information Theory Workshop (ITW)*. IEEE, 2021, pp. 1–6.
<footnote>[21] B. Serbetti, E. Parrinello, and P. Elia, “Multi-access coded caching: gains beyond cache-redundancy,” in *2019 IEEE Information Theory Workshop (ITW)*. IEEE, 2019, pp. 1–5.</footnote>