# Content Delivery over Broadcast Erasure Channels with Distributed Random
Cache

Alireza Vahid  Shih-Chun Lin  I-Hsiang Wang  Yi-Chun Lai Alireza Vahid is with
the Electrical Engineering Department of the University of Colorado Denver,
Denver, CO, USA. Email<EMAIL_ADDRESS>Shih-Chun Lin and Yi-Chun
Lai are with Department of Electrical and Computer Engineering, NTUST, Taipei,
Taiwan. Email<EMAIL_ADDRESS>I-Hsiang Wang is with Department of
Electrical Engineering, National Taiwan University, Taipei, Taiwan. Email:
<EMAIL_ADDRESS>
###### Abstract

We study the content delivery problem between a transmitter and two receivers
through erasure links, when each receiver has access to some random side-
information about the files requested by the other user. The random side-
information is cached at the receiver via the decentralized content placement.
The distributed nature of receiving terminals may also make the erasure state
of two links and indexes of the cached bits not perfectly known at the
transmitter. We thus investigate the capacity gain due to various levels of
availability of channel state and cache index information at the transmitter.
More precisely, we cover a wide range of settings from global delayed channel
state knowledge and a non-blind transmitter (i.e. one that knows the exact
cache index information at each receiver) all the way to no channel state
information and a blind transmitter (i.e. one that only statistically knows
cache index information at the receivers). We derive new inner and outer
bounds for the problem under various settings and provide the conditions under
which the two match and the capacity region is characterized. Surprisingly,
for some interesting cases the capacity regions are the same even with single-
user channel state or single-user cache index information at the transmitter.

##  I Introduction

Available receiver-end side-information can greatly enhance content delivery
and increase the attainable data rates in wireless systems. In particular, in
various applications such as caching [1, 2], coded computing [3], private
information retrieval [4, 5], and index coding [6, 7, 8], side-information is
intentionally and strategically placed at each receiver’s cache during some
placement phase in order to lighten future communication loads. However, in a
more realistic setting, there is no centralized mechanism to populate the
local caches. On the other hand, receivers may obtain some side-information by
simply over-hearing the signals intended for other nodes over the shared
wireless medium. The transmitter(s) may or may not be aware of the exact
content of the side-information at each receiver, and if the transmitter is
not aware of the exact content, the problem is referred to as Blind Index
Coding [9]. Further, the transmitter(s) may be enhanced by receiving channel
state feedback. This paper focuses on content delivery in wireless networks
with potential channel state feedback and/or random available side-information
at the receivers.

In a packet-based communication network, instead of the classic Gaussian
channel, the network-coding-based approaches generally model each
communication hop as a packet erasure channel. In this work, as [10], we focus
on broadcast erasure channels with random receiver side-information. More
specifically, we consider a single transmitter communicating with two
receiving terminals through erasure links. Through decentralized content
placement [9][10], each receiver has randomly cached some side-information
about the message bits (file) of the other user. In [10], for both users,
their indexes of cached bits during the placement and (delayed) channel
erasure state during the delivery are globally known at the transmitter.
However, as pointed out in [11][12], in distributed networks, acquiring such
global information at transmitters is prohibitive due to the extensive date
exchange and the heterogenous capabilities for receiving terminals to feed
back. Thus we consider three scenarios about the transmitter’s knowledge of
the receiver-end side-information: (1) the blind-transmitter case where only
the statistics of the _random_ cache index information is known to the
transmitter, (2) the non-blind-transmitter case where the transmitter knows
exactly what each receiver has access to, and (3) the semi-blind-transmitter
case that knows the exact cache index information at only one of the
receivers. Meanwhile, a range of assumptions on the availability of channel
state information at the transmitter (CSIT) are also considered: (1) when both
receivers provide delayed CSI to the transmitter (DD); (2) when only one
receiver provides delayed CSI to the transmitter (DN); and (3) when receivers
do not provide any CSI to the transmitter (NN).

The blind-transmitter case under scenario NN in [9] corresponds to the setting
that during the whole content placement and delivery, both receivers can not
have capabilities to feed back through the control channel or shared wireless
medium. Then the transmitter has neither cache index information nor CSI. On
the other hand, for each receiver, if the feedback resource is available for
some period of time and then becomes unavailable or intermittent [13, 14],
then we have other scenarios. For example, though during the placement both
receivers can feed back cache indexes, during the delivery one of the receiver
may not be able to feed back the fast varying channel state of its own link.
Then we have a non-blind transmitter under scenario DN. This setting could
also arise due to new security threats that aim to disrupt the flow of control
packets in distributed systems [15, 16, 17], that is, during the delivery the
CSI feedback from one of the receivers is severely attacked.

Related Work and Literature Review: To better place our work within the
literature for cached network or index coding, we summarize some of the main
results in the literature. The classic index coding problem [18, 6, 19]
assumes the transmitter is aware of the exact side-information at each node
[7, 20], and the network does not have wireless links directly. This problem
has been a powerful tool in studying the data communication network with
receiver caching [21, 8, 22].

For index coding over wireless links, as aforementioned, two extreme cases
have been studied [9][10]. In [10], the capacity regions for two and three-
user broadcast erasure channels, when the transmitter has access to global
delayed CSI and cached index information, are characterized. This setting
assumes rather strong and stable feedback channels from all receivers. On the
other hand, blind wireless index coding is introduced in [9] where the
transmitter only knows the statistics of the CSI and cached index information
since there is no feed back at all from the two users. However, a limitation
is added in [9] such that only the user with weaker link (higher erasure
probability) has cache. Even under this limitation, the capacity region is not
fully known In conclusion, there remains a gap in the index coding literature
between these two extreme points when it comes to wireless setting, which is
the target of our paper. More comparisons with [9][10] can be found in Section
III.

Contributions: In this work, we consider the two-user erasure broadcast
channel with the erasure states of the two links being independent of each
other. We first present the capacity for the two-user broadcast erasure
channel with a non-blind transmitter under scenario NN, that is, no CSI
feedback. For scenario NN, we observe that the stronger receiver, _i.e._ the
one whose channel has a smaller erasure probability, will eventually be able
to decode messages intended for both receivers. Note that this observation
does not imply that the broadcast channel is degraded due to the cache.
Interestingly, the achievability derived from this observation indicates that
our optimal protocol works even when the transmitter does not know the exact
cache index information at the stronger receiver, _i.e._ with a “semi-blind”
transmitter. To derive the outer-bounds, besides using the aforementioned
observations, we also show an extremal entropy inequality between the two
receivers that captures the availability of receiver-end side-information.
With a blind transmitter, these outer-bounds can be automatically applied
since the transmitter has more knowledge in the non-blind case, and we show
that the outer bounds can be achieved when the channel is symmetric. When some
delayed CSI is available, we also demonstrate the capacity with a non-blind
transmitter and global CSI (scenario DD) [10] can be achieved when the
transmitter has less information. In particular, for the blind-transmitter
case under scenario DD, we provide an optimal protocol for the symmetric
channel. For the non-blind-transmitter case or semi-blind-transmitter case, we
also extend our earlier non-cached capacity result for scenario DN [12], and
show that even with cache the capacity region with only single-user CSI feed
back can match that with global CSI in [10].

TABLE I: Summary of Contributions Categorized by Transmitter’s Information State | Cache |  Contributions | State | Cache |  Contributions
---|---|---|---|---|---
W | S | W | S |  | W | S | W | S |
✗ | ✗ | ✓ | ✓ |  *$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$ in Theorem 1 | ✓ | ✗ | ✗ | ✓ |  $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DN}}$ in Theorem 2 Case B
✗ | ✗ | ✓ | ✗ |  *$\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{NN}}$ in Corollary 1 | ✗ | ✓ | ✗ | ✗ | Remains open
✗ | ✗ | ✗ | ✓ |  Inner-bounds in Theorem 4 | ✓ | ✓ | ✓ | ✓ |  $\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{DD}}$ previously known [10]
✗ | ✗ | ✗ | ✗ |  Symmetric $\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ in Theorem 3 | ✓ | ✓ | ✓ | ✗ |  $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DD}}$ in Theorem 2 Case B
✗ | ✓ | ✓ | ✓ |  *$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{DN}}$ in Theorem 2 Case C | ✓ | ✓ | ✗ | ✓ |  $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DD}}$ in Theorem 2 Case B
✗ | ✓ | ✓ | ✗ |  $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DN}}$ in Theorem 2 Case B | ✓ | ✓ | ✗ | ✗ |  Symmetric $\mathcal{C}^{\mathrm{blind}}_{\mathrm{DD}}$ in Theorem 2 Case A

Table I summarizes our contributions, which we will further elaborate upon in
Section III. In this table, “W” stands for the weak user (the one with higher
erasure probability) and “S” stands for the strong user. Further, “State”
columns are for CSIT, and “Cache” columns are for the transmitter’s knowledge
of bit indices cached at the receiver: “✓” indicates availability and “✗”
indicates missing information. For example, “✗✗✓✗” is the no CSI case (NN)
with semi-blind Tx that knows the cache index information at the weaker
receiver. For the three cases marked with “*”, the capacity regions are fully
identified without additional limitations on system parameters.

Paper Organization: The rest of the paper is organized as follows. In Section
II, we present the problem setting and the assumptions we make in this work.
Section III presents the main contributions and provides further insights and
interpretations of the results. The proof of the main results will be
presented in the following sections. Finally, Section VIII concludes the
paper.

##  II Problem Formulation

Following [10], we consider the canonical two-user broadcast erasure channel
in Figure 1 to understand how transmitters can exploit the available side-
information at the receivers to improve the capacity region. In this network,
a transmitter, $\mathsf{Tx}$, wishes to transmit two independent messages
(files), $W_{1}$ and $W_{2}$, to two receiving terminals $\mathsf{Rx}_{1}$ and
$\mathsf{Rx}_{2}$, respectively, over $n$ channel uses. Each message, $W_{i}$,
contains $m_{i}$ data packets (or bits) which we denote by
$\vec{a}=\left(a_{1},a_{2},\ldots,a_{m_{1}}\right)$ for $\mathsf{Rx}_{1}$, and
by $\vec{b}=\left(b_{1},b_{2},\ldots,b_{m_{2}}\right)$ for $\mathsf{Rx}_{2}$.
Here, we note that each packet is a collection of encoded bits, however, for
simplicity and without loss of generality, we assume each packet is in the
binary field, and we refer to them as bits. Extensions to broadcast packet
erasure channels where packets are in large finite fields are straightforward
as in [10][23].

Channel model: At time instant $t$, the messages are mapped to channel input
$X[t]\in\mathbb{F}_{2}$, and the corresponding received signals at
$\mathsf{Rx}_{1}$ and $\mathsf{Rx}_{2}$ are

$\displaystyle
Y_{1}[t]=S_{1}[t]X[t]~{}~{}\;\mbox{and}\;~{}~{}Y_{2}[t]=S_{2}[t]X[t],$ (1)

respectively, where $\left\\{S_{i}[t]\right\\}$ denotes the Bernoulli
$(1-\delta_{i})$ process that governs the erasure at $\mathsf{Rx}_{i}$, and is
independently and identically distributed (i.i.d.) over time and across users.
When $S_{i}[t]=1$, $\mathsf{Rx}_{i}$ receives $X[t]$ noiselessly; and when
$S_{i}[t]=0$, it receives an erasure. In other words, as we assume receivers
are aware of their local channel state information, each receiver can map the
received signal when $S_{i}[t]=0$ to an erasure.

CSI assumptions: We assume the receivers are aware of the channel state
information (_i.e._ global CSIR). For the transmitter, on the other hand, we
assume the following scenarios:

  1. 1.

NN or No CSIT model: The transmitter knows only the erasure probabilities and
not the actual channel realizations;

  2. 2.

DN model: The transmitter knows the erasure probabilities and the actual
channel realizations of one receiver with unit delay;

  3. 3.

DD or delayed CSIT model: The transmitter knows the erasure probabilities and
the actual channel realizations of both receivers with unit delay.

Figure 1: Two-user broadcast erasure channels with channel state feedback and
random side-information at each receiver.

Available receiver side-information: Decentralized content placement [9][10]
is adopted, where each user independently caches a subset of the message bits
(file). In particular, we assume a random fraction $(1-\epsilon_{i})$ of the
bits intended for receiver $\mathsf{Rx}_{\bar{i}}$ is cached at
$\mathsf{Rx}_{{i}}$, $\bar{i}\overset{\triangle}{=}3-i$, and we denote this
side information with $W_{\bar{i}|i}$ as in Figure 1. This assumption on the
available side-information at each receiver could also be represented using an
erasure side channel. More precisely, we can assume available side-information
to receiver $i$ is created through

$\displaystyle
E_{i}[\ell]W_{\bar{i}}[\ell],\qquad\ell=1,2,\ldots,nR_{\bar{i}},$ (2)

where $W_{\bar{i}}[\ell]$ is the $\ell^{\mathrm{th}}$ bit of message
$W_{\bar{i}}$, while the cache index information $E_{i}[\ell]$ is an i.i.d.
Bernoulli $(1-\epsilon_{i})$ process independent of all other channel
parameters and known at receiver $i$. To concisely present our result, in our
placement model each user does not cache its own message but only the
interference. Our results can be easily extended to the case when both the own
message and interference bits are cached.

The Transmitter’s knowledge of the cache index: Following the convention which
presents the length $nR_{\bar{i}}$ sequence $E_{i}[1],\ldots
E_{i}[nR_{\bar{i}}]$ as $E^{nR_{\bar{i}}}_{i}$, we consider three scenarios
for the blindness of the cache index at the transmitter

  1. 1.

Blind Transmitter: In this scenario, the transmitter’s knowledge of the
receiver side-information is limited to the values of $\epsilon_{1}$ and
$\epsilon_{2}$, while the cache index information $E^{nR_{2}}_{1}$ and
$E^{nR_{1}}_{2}$ in (2) is unknown.

  2. 2.

Semi-Blind Transmitter: In this scenario, the transmitter’s knowledge of the
side-information at $\mathsf{Rx}_{i}$ is limited to the value of
$\epsilon_{i}$, while the transmitter knows $W_{i|\bar{i}}$ through
$E^{nR_{i}}_{\bar{i}}$

  3. 3.

Non-Blind Transmitter: In this scenario, the transmitter knows exactly what
fraction of each message is available to the unintended receiver. In other
words, the transmitter knows $W_{2|1}$ and $W_{1|2}$ through the the cache
index information $E^{nR_{2}}_{1}$ and $E^{nR_{1}}_{2}$.

Encoding: We start with the NN model where the constraint imposed at the
encoding function $f_{t}(.)$ at time index $t$ for the blind scenario is

$\displaystyle X[t]=f_{t}\left(W_{1},W_{2},\mathsf{PI}\right),$ (3)

for the non-blind scenario is

$\displaystyle
X[t]=f_{t}\left(W_{1|2},\bar{W}_{1|2},W_{2|1},\bar{W}_{2|1},\mathsf{PI}\right),$
(4)

and

$\displaystyle
X[t]=f_{t}\left(W_{i|\bar{i}},\bar{W}_{i|\bar{i}},W_{\bar{i}},\mathsf{PI}\right),$
(5)

where $\mathsf{PI}$ represents the knowledge of statistical parameters
$\delta_{1},\delta_{2},\epsilon_{1},$ and $\epsilon_{2}$, and
$\bar{W}_{i|\bar{i}}$ is the complement of $W_{i|\bar{i}}$ with respect to
$W_{i}$, $i=1,2$. Although not ideal, this notation is adopted to highlight
the transmitter’s knowledge of the available side-information at the
receivers.

For the DD case, $S^{t-1}$ is added to the inputs of $f_{t}(.)$, while under
DN model, only of the channels is revealed to the transmitter up to time
$(t-1)$. Rather than enumerating all possibilities, we present an example, to
clarify the encoding constraints. Suppose the transmitter is knows the side-
information available to $\mathsf{Rx}_{2}$ (semi-blind), and has access to the
delayed CSI from $\mathsf{Rx}_{1}$ (DN model), then, we have

$\displaystyle
X[t]=f_{t}\left(W_{1|2},\bar{W}_{1|2},W_{2},S_{1}^{t-1},\mathsf{PI}\right),$
(6)

Decoding: Each receiver $\mathsf{Rx}_{i}$, $i=1,2$ knows its own CSI across
entire transmission block $S^{n}_{i}$, and the CSI $S^{n}_{\bar{i}}$ if the
other receiver $\bar{i}$ provides feedback. Under scenario NN it uses a
decoding function
$\varphi_{i,n}\left(Y_{i}^{n},S_{i}^{n},W_{\bar{i}|i}\right)$ to get an
estimate $\widehat{W}_{i}$ of $W_{i}$, while under scenario DD the decoding
function becomes $\varphi_{i,n}\left(Y_{i}^{n},S^{n},W_{\bar{i}|i}\right)$
where $S^{n}=(S_{1}^{n},S^{n}_{2})$. Note that under scenario DN, only the no-
feedback receiver has global $S^{n}$. An error occurs whenever
$\widehat{W}_{i}\neq W_{i}$. The average probability of error is given by

$\displaystyle\lambda_{i,n}=\mathbb{E}[P(\widehat{W}_{i}\neq W_{i})],$ (7)

where the expectation is taken with respect to the random choice of the
transmitted messages.

Capacity region: We say that a rate pair $(R_{1},R_{2})$ is achievable, if
there exists a block encoder at the transmitter, and a block decoder at each
receiver, such that $\lambda_{i,n}$ goes to zero as the block length $n$ goes
to infinity. The capacity region, $\mathcal{C}$, is the closure of the set of
the achievable rate pairs. Throughout the paper, we will distinguish the
capacity region under different assumptions. For example,
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ is the capacity region of the
two-user broadcast erasure channels with a blind transmitter and no CSIT.

##  III Main Results

In this section, we present the main contributions of this paper and provide
some insights and intuitions about the findings.

###  III-A Statement of the Main Results

We start with scenarios in which we characterize the capacity region, and
then, we present cases for which we derive new inner-bounds. In Theorem 1, for
the no CSIT scenario, we establish the capacity region with a non-blind
transmitter. We will highlight the importance of side-information at the
weaker receiver and how a semi-blind transmitter may achieve the same region
in Remarks 2 and 1, respectively. Next, we present new capacity results when
(some) delayed CSI is available to the transmitter in Theorem 2. Next, for the
no CSIT assumption and a blind transmitter, in Theorem 3 we present new
conditions beyond [9] under which the capacity region is achievable, and a new
achievable region is presented in Theorem 4.

######  Theorem 1.

For the two-user broadcast erasure channel with a non-blind transmitter and no
CSIT as described in Section II, we have

$\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{NN}}\equiv\left\\{\begin{array}[]{ll}0\leq\beta^{\mathrm{no}}_{1}R_{1}+R_{2}\leq\left(1-\delta_{2}\right),&\\\
0\leq
R_{1}+\beta^{\mathrm{no}}_{2}R_{2}\leq\left(1-\delta_{1}\right).&\end{array}\right.$
(8)

where

$\displaystyle\beta^{\mathrm{no}}_{i}=\epsilon_{\bar{i}}\min\left\\{\frac{1-\delta_{\bar{i}}}{1-\delta_{i}},1\right\\}.$
(9)

The derivation of the outer-bounds has two main ingredients. First, as
detailed in upcoming Remark 1, even the channel is not degraded, the stronger
receiver can decode both messages regardless of the values of $\epsilon_{1}$
and $\epsilon_{2}$ for receiver cache. Second, as detailed in upcoming Lemma
2, we derive an extremal entropy inequality between the two receivers that
captures the availability of receiver-end side-information, including the
channel state and cache index information. The outer-bound region holds for
the non-blind setting and thus, includes the capacity region with a blind
transmitter as well. The following two remarks provide further insights.

######  Remark 1 (Simplified expressions and degradedness).

Without loss of generality, assume $\delta_{2}\geq\delta_{1}$, meaning that
receiver $1$ has a stronger channel. Then, the region of Theorem 1 can be
written as

$\left\\{\begin{array}[]{ll}0\leq\epsilon_{2}\frac{1-\delta_{2}}{1-\delta_{1}}R_{1}+R_{2}\leq\left(1-\delta_{2}\right),&\\\
0\leq R_{1}+\epsilon_{1}R_{2}\leq\left(1-\delta_{1}\right).\end{array}\right.$
(10)

Unlike the scenario with no side-information at the receivers, this assumption
does not mean the channel is degraded. However, the stronger receiver, ${\sf
Rx}_{1}$ in this case, will be able to decode both $W_{1}$ and $W_{2}$ by end
of the communication block regardless of the values of $\epsilon_{1}$ and
$\epsilon_{2}$. The reason is as follows. After decoding $W_{1}$, receiver
${\sf Rx}_{1}$ has access to the side-information of receiver ${\sf Rx}_{2}$,
_i.e._ $W_{1|2}$, and can emulate the channel of ${\sf Rx}_{2}$ as it has a
stronger channel ($\delta_{2}\geq\delta_{1}$). Finally, we note that although
the stronger receiver is able to decode both messages, this does not imply
that the stronger receiver will have a higher rate. As an example, suppose
$\delta_{1}=1/3,\delta_{2}=1/2,\epsilon_{1}=2/3,$ and $\epsilon_{2}=1/6$.
Then, from the Theorem 1, the maximum sum-rate point is:

$\displaystyle\left(R_{1},R_{2}\right)=\left(\frac{4}{11},\frac{5}{11}\right).$
(11)

######  Remark 2 (Importance of side-information at the weaker receiver).

Under the same assumption of the previous remark, $\delta_{2}\geq\delta_{1}$,
from the outer-bounds of Theorem 1, we conclude that if the weaker receiver
has no side-information, _i.e._ $\epsilon_{2}=1$, then, the capacity region is
the same as having no side-information at either receivers. In other words, as
long as the weaker receiver has no side-information, additional information at
the stronger receiver does not enlarge the region. On other other hand, any
side-information at the weaker receiver results in an outer-bound region that
is strictly larger than the capacity region with no side-information at either
receivers.

Based on these remarks, we can provide more details on the achievability
protocol. Under the no-CSIT assumption, the stronger receiver will eventually
be able to decode both messages. Thus, the first step is to deliver the
message intended for the weaker receiver. The stronger receiver will be able
to decode this message faster than the intended receiver and thus, in the
second step, we include the part of the message for the stronger user that is
available at the weaker receiver. In other words, this second step is
beneficial to both receivers. We note that to accomplish this task, the
transmitter at least needs to know the side-information of the weaker
receiver. This latter fact is further explained in the Corollary below. During
the final step, the remaining part of the message intended for the stronger
receiver is delivered.

As will be detailed in Section V, to achieve the outer-bounds, indeed the
transmitter only needs to know the side-information available to the weaker
receiver. Thus, we have

######  Corollary 1.

The capacity region with a semi-blind transmitter $\mathcal{C}^{\mathrm{semi-
blind}}_{\mathrm{NN}}$ equals to $\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{NN}}$ in Theorem 1 if the cache index information (2) of the
weaker receiver (link with larger erasure probability) is known at the
transmitter.

The following lemma from [10] establishes the outer-bounds on the capacity
region of the two-user broadcast erasure channel with a non-blind transmitter
and delayed CSIT, $\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{DD}}$. We provide
several new achievability strategies to achieve these bounds when the
transmitter has less knowledge compared to what these bounds assume, and
establish interesting capacity results.

######  Lemma 1 ([10]).

For the two-user broadcast erasure channel with a non-blind transmitter and
delayed CSIT as described in Section II, we have outer-bound region

$\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{DD}}\subseteq\left\\{\begin{array}[]{ll}\vspace{1mm}0\leq
R_{i}\leq(1-\delta_{i}),&i=1,2,\\\
\beta^{\mathrm{delayed}}_{i}R_{i}+R_{\bar{i}}\leq\left(1-\delta_{\bar{i}}\right),&i=1,2.\end{array}\right.$
(12)

where

$\displaystyle\beta^{\mathrm{delayed}}_{i}=\epsilon_{\bar{i}}\frac{1-\delta_{\bar{i}}}{1-\delta_{1}\delta_{2}}.$
(13)

Now, we show that this outer-bound region is achievable under the following
scenarios.

######  Theorem 2.

For the two-user broadcast erasure channel, the capacity region is achieved
when:
Case A: with a blind transmitter and global delayed CSIT, the capacity region
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{DD}}$ equals to (12) when the channel
is symmetric (_i.e._ $\delta_{1}=\delta_{2}=\delta$ and
$\epsilon_{1}=\epsilon_{2}=\epsilon$);

Case B: with the transmitter knowing full side-information from one receiver
and only the delayed CSI of the other receiver (e.g., the semi-blind-
transmitter case with $\epsilon_{1}=0$ for $\mathsf{Rx}_{1}$), the capacity
region $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DN}}$ (and thus
$\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DD}}$) equals to (12)

Case C: with a non-blind transmitter having access to only the delayed CSI of
one receiver, the capacity region $\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{DN}}$ equals to (12).

Note that having full side-information at a receiver (as in Case B above)
immediately implies the transmitter is not blind with respect to that
receiver. For the blind-transmitter case, if $\epsilon_{i}=0$ then the
transmitter knows $\mathsf{Rx}_{i}$ has full side-information, and thus
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{DN}}$ is also partially known from Case
B.

Without the global channel state and/or cache index information from both
receivers, our new achievability results of Theorem 2 differ significantly
from the those in [10]. In particular in [10], overheard bits and cached bits
are both known at the transmitter to create network coding opportunities
simultaneously benefit for both receivers. In our achievability, network
coding opportunities can only be opportunistically created. Rather
interestingly, in three cases identified by our Theorem, transmitter blindness
or one-sided feedback may not result in any capacity loss compared with [10].

To achieve capacity $\mathcal{C}^{\mathrm{blind}}_{\mathrm{DD}}$ in Case A, we
present an opportunistic protocol where the transmitter first sends out linear
combinations of the packets for both receivers. Then, using the feedback
signals and the fact that some of the packets for one receiver are available
at the other, the transmitter sends bits for intended for one receiver in such
as way to help one receiver remove interference and the other to obtain new
information about its bits. Depending on channel parameters, this may follow
with a multicast phase. This idea could be interpreted as an opportunistic
reverse network coding for erasure channels. Both Cases B and C focus on
cached capacity with only single-user delayed CSI. Interestingly, our four-
phase opportunistic network coding for Case C will also create blind side-
information at the “N” user for the recycled bits. Indeed, the last two phases
in Case C is modified form the achievability for Case B. Compared with [12],
the new ingredient for Case C is the non-blind cache, and we propose to
generalize [12] by carefully mixing the fresh cached bits with the recycled
un-cached bits. Specifically, the recycling in [12] is done by mixing two pre-
encoded bit sequences. On the contrary to [12] where the input sequence of
each pre-encoder is always recycled, it may contain fresh bits in our Case C
as detailed in Sec. VII.

The following two theorems focus on the no-CSIT blind-transmitter assumption.
The first one identifies conditions under which the outer-bound region of
Theorem 1 can be achieved even when the transmitter does not know what side-
information is available to each receiver. The second theorem presents an
achievable region when the stronger receiver has full side-information, but
this achievable region does not match the outer-bounds.

######  Theorem 3.

For the two-user broadcast erasure channel with no channel feedback, a blind
transmitter, and available receiver side-information as described in Section
II, the capacity $\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ equals to
$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$ in Theorem 1 when:

  1. 1.

When $\delta_{2}\geq\delta_{1}$ and $\epsilon_{2}\in\\{0,1\\}$;

  2. 2.

Symmetric setting: when $\delta_{1}=\delta_{2}=\delta$, and
$\epsilon_{1}=\epsilon_{2}=\epsilon$.

######  Theorem 4.

For the two-user broadcast erasure channel with no channel feedback, a blind
transmitter, as described in Section II, when $\delta_{2}\geq\delta_{1}$ and
$\epsilon_{1}=0$, we can the following region is achievable:

$\mathcal{R}^{\mathrm{in}}\equiv\left\\{\begin{array}[]{ll}0\leq\left(\epsilon_{2}+\delta_{1}(1-\epsilon_{2})\right)\frac{1-\delta_{2}}{1-\delta_{1}}R_{1}+R_{2}\leq\left(1-\delta_{2}\right),&\\\
0\leq R_{1}\leq\left(1-\delta_{1}\right).&\end{array}\right.$ (14)

We note that for $\delta_{1}=0$ (no erasure at the stronger receiver), the
inner-bound region of Theorem 4 matches the outer-bounds of Theorem 1, _i.e._
$\mathcal{R}^{\mathrm{in}}\equiv\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ .

Note that the blind-transmitter case under no-CSIT was also considered in [9]
but only the weaker receiver has side-information. In that setting, outer and
inner bounds were presented that match only when erasure probabilities are
equal to zero, which is no longer an erasure setting. In contrast, in this
work, we have the capacity region $\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{NN}}$ in Theorem 1 for the non-blind-transmitter case, which
recovers the outer-bounds of [9] as a special case. The capacity region
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ of blind index coding over no-
CSIT broadcast erasure channel remains open in general.

###  III-B Illustration of the results

In this subsection, we briefly illustrate the results through a few examples
to further clarify and discuss some of the insights and intuitions provided
above.

We start with Theorem 2 where the transmitter has access to (some) delayed
CSI. Figure 2 illustrates the capacity region
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{DD}}=\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{DN}}$ from Theorem 2 when $\delta_{1}=\delta_{2}=\delta=0.5$
and $\epsilon_{1}=\epsilon_{2}=\epsilon\in\\{0,0.5,1\\}$. In particular,
$\epsilon=1$ is the case in which no side-information is available and our
results recover [24]. The other extreme is $\epsilon=0$ where the entire
message of one user is available to the other and maximum individual point-to-
point rates can be achieved. Finally, $\epsilon=0.5$ is an intermediate case
and the capacity is strictly larger than that of no side-information.

Figure 2: Capacity region
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{DD}}=\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{DN}}$ for $\delta_{1}=\delta_{2}=\delta=0.5$ and
$\epsilon_{1}=\epsilon_{2}=\epsilon\in\\{0,0.5,1\\}$.

We then consider the no-CSIT scenario. For the first example in this case, we
consider $\delta_{1}=\frac{1}{2}$ and $\delta_{2}=\frac{3}{4}$. The capacity
region of the broadcast erasure channel with these parameters and no side-
information at either receiver is described by all non-negative rates
satisfying:

$\displaystyle\frac{1}{2}R_{1}+R_{2}\leq\frac{1}{4}.$ (15)

Note that we no side-information, the channel is degraded. Further, as
discussed earlier, as long as the weaker receiver (${\sf Rx}_{2}$ in this
case) has no side-information, _i.e._ $\epsilon_{2}=1$, the capacity region
remains identical to the one described in (15) with no side-information at
either receivers. This region is included in Figure 3(a) and (b) as benchmark.
Note that significant caching or index coding gains are obtained for all
settings presented in Figure 3(a) and (b).

Figure 3: (a) Illustration of the capacity region $\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{NN}}$ when ${\sf Rx}_{i}$ has full side-information
($\epsilon_{i}=0$); (b) increase in the achievable rates as $\epsilon_{1}$
goes from $1$ to $0$ for $\epsilon_{2}=0.5$.

Next, we examine the region $\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$
when one receiver has full side-information. Figure 3(a) includes both these
cases and depicts how the capacity region enlarges as more side-information is
available to the receivers. We note that with full side-information at both
receivers ($\epsilon_{1}=\epsilon_{2}=0$), maximum individual rates given by
$R_{i}=(1-\delta_{i})$, $i=1,2$, are achievable simultaneously. Figure 3(b)
depicts the gradual increase in achievable rates when
$\epsilon_{2}=\frac{1}{2}$ and $\epsilon_{1}$ goes from $1$ (no side
information) to $0$ (full side-information). Note that receiver ${\sf Rx}_{1}$
has a stronger channel so the illustrated region also equals to the capacity
region $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{NN}}$ when the transmitter
has no cache index information of ${\sf Rx}_{1}$.

Figure 4: (a) Although the stronger receiver will always be able to decode
both messages, the weaker receiver may have a higher rate. In this example for
$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$, we have
$\delta_{1}=\frac{1}{3},\delta_{2}=\frac{1}{2},\epsilon_{1}=\frac{2}{3},$ and
$\epsilon_{2}=\frac{1}{6}$; (b) Capacity region with symmetric parameters
$\delta_{1}=\delta_{2}=\delta$ and $\epsilon_{1}=\epsilon_{2}=\epsilon$. The
maximum sum-rate point is given by $\frac{2(1-\delta)}{(1+\epsilon)}$. The
capacity region with symmetric parameters can be achieved under the blind-
transmitter scenario as well. See Theorem 3.

As the second example, we consider $\delta_{1}=\frac{1}{3}$ and
$\delta_{2}=\frac{1}{2}$. Similar to the previous case for capacity region
$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$, receiver ${\sf Rx}_{1}$ has
a stronger channel. However, as illustrated in Figure 4(a), with
$\epsilon_{1}=\frac{2}{3}$ and $\epsilon_{2}=\frac{1}{6}$, the weaker receiver
has a higher rate as given in (11). Finally, Figure 4(b) depicts the capacity
region $\mathcal{C}^{\mathrm{non-
blind}}_{\mathrm{NN}}=\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ with
symmetric channel parameters ($\delta_{1}=\delta_{2}=\delta$ and
$\epsilon_{1}=\epsilon_{2}=\epsilon$): with no side-information, the maximum
achievable sum-rate is $(1-\delta)$; and with side-information (even blind),
the maximum sum-rate is given by:

$\displaystyle\frac{2(1-\delta)}{(1+\epsilon)}.$ (16)

Figure 5: Comparing the inner-bounds of Theorem 4 for
$\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ to the outer-bounds of Theorem 1
for $\delta_{2}\geq\delta_{1}$ and $\epsilon_{1}=0$. Black dashed lines define
the outer-bound region, while the solid green lines are the inner-bounds. The
shaded area is the gap between the two.

Finally, Figure 5 illustrates the outer-bounds of Theorem 1 and the inner-
bounds of Theorem 4 for $\delta_{2}\geq\delta_{1}$ and $\epsilon_{1}=0$. In
other words, in this case, the stronger receiver has full side-information. We
note that the inner-bounds of Theorem 4 for the blind-transmitter case match
the outer-bounds when $\delta_{1}=0$.

###  III-C Organization of the Proofs

In the following sections, we provide the proof of our main contributions. We
prove the capacity region of Theorem 1 in Sections IV and V. We then move to
the achievability part of Theorem 2 as they are capacity-achieving and include
several interesting new ingredients, as in Section VI and VII. The proofs of
other results are deferred to the Appendix.

##  IV Converse Proof of $\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$ in
Theorem 1

In this section, we derive the outer-bounds of Theorem 1. We note that as the
capacity region of the non-blind setting includes that of the blind
assumption, the derivation in this section is for the non-blind transmitter
case and the bounds apply to the blind-transmitter case as well.

The point-to-point outer-bounds, _i.e._ $R_{i}\leq(1-\delta_{i})$, are those
of erasure channels, and thus, omitted. Without loss of generality, we assume
$\delta_{2}\geq\delta_{1}$, meaning that receiver $1$ has a stronger channel.
As discussed in Remark 1, unlike the scenario with no side-information at the
receivers, this assumption does not mean the channel is degraded. In what
follows, we derive the following outer-bounds:

$\displaystyle\mathbf{B1}:\frac{\epsilon_{2}(1-\delta_{2})}{(1-\delta_{1})}R_{1}+R_{2}\leq\left(1-\delta_{2}\right),$
$\displaystyle\mathbf{B2}:R_{1}+\epsilon_{1}R_{2}\leq\left(1-\delta_{1}\right).$
(17)

Suppose rate-tupe $\left(R_{1},R_{2}\right)$ is achievable. We first derive
$\mathbf{B2}$ to get some insights.

Derivation of $\mathbf{B2}$: As discussed in Remark 1, the stronger receiver,
${\sf Rx}_{1}$ in this case, is able to decode both messages by the end of the
communication block using its available side information. Thus, we have

$\displaystyle H(W_{1}|G^{n})+H(\bar{W}_{2|1}|G^{n})\leq$ $\displaystyle
I(W_{1},\bar{W}_{2|1};Y_{1}^{n}|W_{2|1},G^{n})+n\upxi_{n}\leq
H(Y_{1}^{n}|W_{2|1},G^{n})+n\upxi_{n}\leq n(1-\delta_{1})+n\upxi_{n}.$ (18)

We also note that

$\displaystyle
nH(\bar{W}_{2|1}|G^{n})=\sum^{m_{2}}_{\ell=1}H\big{(}(1-E_{1}[\ell])W_{2}[\ell]\big{|}E_{1}[\ell]\big{)}=n\epsilon_{1}H(W_{2})=n\epsilon_{1}R_{2}.$
(19)

Thus, from (IV) and (19), we get

$\displaystyle n(R_{1}+\epsilon_{1}R_{2})\leq n(1-\delta_{1})+n\upxi_{n}.$
(20)

Dividing both sides by $n$ and let $n\rightarrow\infty$, we get the second
outer-bound in (IV).

Derivation of $\mathbf{B1}$: We enhance receiver $\mathsf{Rx}_{1}$ by
providing the entire $W_{2}$ to it, as opposed to the already available
$W_{2|1}$, and we note that this cannot reduce the rates. Moreover, motivated
from the Derivation of $\mathbf{B2}$, this enhancement should only have
limited rate increase. From the decentralized placement model (2), we define
the global channel state and cache index information as

$G^{n}:=\\{S^{n}_{1},S^{n}_{2},E^{nR_{2}}_{1},E^{nR_{1}}_{2}\\}:=\\{S^{n},E^{n}\\}$
(21)

then, using

$\displaystyle\beta_{1}^{\mathrm{no}}=\frac{\epsilon_{2}(1-\delta_{2})}{(1-\delta_{1})},$
(22)

we have

$\displaystyle n$
$\displaystyle\left(\beta_{1}^{\mathrm{no}}R_{1}+R_{2}\right)=\beta_{1}^{\mathrm{no}}H(W_{1})+H(W_{2})$
$\displaystyle\overset{(a)}{=}\beta_{1}^{\mathrm{no}}H(W_{1}|W_{2},G^{n})+H(W_{2}|W_{1|2},G^{n})$
$\displaystyle\overset{(\mathrm{Fano})}{\leq}\beta_{1}^{\mathrm{no}}I(W_{1};Y_{1}^{n}|W_{2},G^{n})+I(W_{2};Y_{2}^{n}|W_{1|2},G^{n})+n\upxi_{n}$
$\displaystyle=\beta_{1}^{\mathrm{no}}H(Y_{1}^{n}|W_{2},G^{n})-\beta_{1}^{\mathrm{no}}\underbrace{H(Y_{1}^{n}|W_{1},W_{2},G^{n})}_{=~{}0}$
$\displaystyle\quad+H(Y_{2}^{n}|W_{1|2},G^{n})-H(Y_{2}^{n}|W_{1|2},W_{2},G^{n})+n\upxi_{n}$
$\displaystyle\overset{(b)}{\leq}H(Y_{2}^{n}|W_{1|2},G^{n})+2n\upxi_{n}$
$\displaystyle\overset{(c)}{\leq}n\left(1-\delta_{2}\right)+2\upxi_{n},$ (23)

where $\upxi_{n}\rightarrow 0$ as $n\rightarrow\infty$; $(a)$ follows from the
independence of messages and captures the enhancement of receiver
$\mathsf{Rx}_{1}$; $(b)$ follows from Lemma 2 below; $(c)$ is true since the
entropy of a binary random variable is at most one and the channel to the
second receiver is only on a fraction $\left(1-\delta_{2}\right)$ of the
communication time. Dividing both sides by $n$ and let $n\rightarrow\infty$,
we get the first outer-bound in (IV).

######  Lemma 2.

For the two-user broadcast erasure channel with no channel feedback but with
non-blind side information at the receivers as described in Section II,
whether blind or not, and $\beta_{1}^{\mathrm{no}}$ given in (9), we have

$\displaystyle
H\left(Y_{2}^{n}|W_{1|2},W_{2},G^{n}\right)+n\upxi_{n}\geq\beta_{1}^{\mathrm{no}}H\left(Y_{1}^{n}|W_{2},G^{n}\right),$
(24)

where $\upxi_{n}\rightarrow 0$ as $n\rightarrow\infty$, where $G^{n}$ is the
global channel state and cache index information in (21).

###### Proof.

We first have the following fact

$\displaystyle
H\left(Y_{2}^{n}|W_{1|2},W_{2},G^{n}\right)\geq\frac{1-\delta_{2}}{1-\delta_{1}}H\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right),$
(25)

which is modified from our previous result [25]. For completeness, we still
present the details in Appendix A. Now, to prove this Lemma with (25), we note
that

$0=H\left(Y_{1}^{n}|W_{1},W_{2},G^{n}\right)=H\left(Y_{1}^{n}|W_{1|2},\bar{W}_{1|2},W_{2},G^{n}\right),$
(26)

where $\bar{W}_{1|2}$ is the complement of $W_{1|2}$ in $W_{1}$, and then

$\displaystyle
H\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right)=I(\bar{W}_{1|2};Y_{1}^{n}|W_{1|2},W_{2},G^{n})$
$\displaystyle=$ $\displaystyle
H(\bar{W}_{1|2}|W_{1|2},W_{2},G^{n})-H(\bar{W}_{1|2}|Y_{1}^{n},W_{1|2},W_{2},G^{n}).$
(27)

Since $H\left(W_{1}|Y_{1}^{n},W_{2},G^{n}\right)\leq n\upxi_{n},$ the second
term in the RHS of (27) will also be less than $n\upxi_{n}$ due to the
$W_{1}=(W_{1|2},\bar{W}_{1|2})$ and the chain rule. For the first term in the
RHS, as (19), it equals to $H(\bar{W}_{1|2}|E_{2}^{n})=\epsilon_{2}H(W_{1}).$
Then we get

$\displaystyle H$
$\displaystyle\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right)\geq\epsilon_{2}H\left(W_{1}\right)-n\upxi_{n}\overset{(a)}{\geq}\epsilon_{2}H\left(Y_{1}^{n}|W_{2},G^{n}\right)-n\upxi_{n},$
(28)

and $(a)$ is obtained from (26) as

$\displaystyle H\left(Y_{1}^{n}|W_{1},W_{2},G^{n}\right)=0\Rightarrow
H\left(W_{1}\right)\geq H\left(Y_{1}^{n}|W_{2},G^{n}\right).$

Finally, from (25) and (28), we obtain

$\displaystyle H$
$\displaystyle\left(Y_{2}^{n}|W_{1|2},W_{2},G^{n}\right)\overset{\eqref{Eq:withSideInfoN}}{\geq}\frac{1-\delta_{2}}{1-\delta_{1}}H\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right)$
$\displaystyle\overset{\eqref{Eq:RemovingSideInfoN}}{\geq}\frac{\epsilon_{2}\left(1-\delta_{2}\right)}{\left(1-\delta_{1}\right)}H\left(Y_{1}^{n}|W_{2},G^{n}\right)-n\upxi_{n}$
$\displaystyle\overset{\eqref{Eq:Beta_No}}{=}\beta_{1}^{\mathrm{no}}H\left(Y_{1}^{n}|W_{2},G^{n}\right)-n\upxi_{n}.$
(29)

This completes the proof of Lemma 2. ∎

##  V Achievability Proof of $\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$
in Theorem 1

In this section, we provide an achievability protocol for the non-blind
transmitter case, and we show that the achievable regions matches the outer-
bounds of Theorem 1. Thus, we characterize the capacity region of the problem
when the transmitter is aware of the available side-information at the
receivers. For the proof, without loss of generality, we assume
$\delta_{2}\geq\delta_{1}$, meaning that ${\sf Rx}_{1}$ has a stronger channel
than ${\sf Rx}_{2}$.

Our achievability proof reveals a surprising result, only the cache index
information $E^{nR_{1}}_{2}$ of the weaker receiver 2 in (2) is needed at the
transmitter. Thus the transmitter can be semi-blind as Corollary 1 to achieve
the outer-bounds. As a warm-up, we first focus on an example where
$\epsilon_{2}=0$. In this case, receiver ${\sf Rx}_{2}$ (the weaker receiver)
has full side-information of the message for ${\sf Rx}_{1}$, _i.e._
$W_{1|2}=W_{1}$, and receiver ${\sf Rx}_{1}$ has access to $(1-\epsilon_{1})$
of the bits intended for ${\sf Rx}_{2}$. The outer-bounds of Theorem 1 in this
case become:

$\left\\{\begin{array}[]{ll}0\leq R_{2}\leq\left(1-\delta_{2}\right),&\\\
0\leq R_{1}+\epsilon_{1}R_{2}\leq\left(1-\delta_{1}\right).\end{array}\right.$
(30)

Thus, the non-trivial corner point is given by:

$\displaystyle R_{1}=(1-\delta_{1})-\epsilon_{1}(1-\delta_{2}),$
$\displaystyle R_{2}=(1-\delta_{2}).$ (31)

In this case, we set

$\displaystyle\eta=\frac{R_{1}}{R_{2}}=\frac{(1-\delta_{1})}{(1-\delta_{2})}-\epsilon_{1}>0.$
(32)

Achievability protocol for $\epsilon_{2}=0$ : Recall $\eta=m_{1}/m_{2}$, we
start with $m$ bits for ${\sf Rx}_{2}$ and $\eta m$ bits for ${\sf Rx}_{1}$.
The achievability protocol is carried a single phase with two segments
(another Phase will be added later for general $\epsilon_{2}$). The total
communication time is set to $\frac{m}{(1-\delta_{2})}.$

Segment a: This segment has a total length of

$\displaystyle
t_{a}=\frac{\epsilon_{1}m}{(1-\delta_{1})}<\frac{m}{(1-\delta_{2})},$ (33)

where the last inequality is from $R_{1}>0$ in (V). During this segment, the
transmitter sends $t_{a}$ of the random combinations of the $m$ bits intended
for ${\sf Rx}_{2}$. During this segment, stronger ${\sf Rx}_{1}$ obtains

$\displaystyle(1-\delta_{1})t_{a}=\epsilon_{1}m$ (34)

random equations of the $m$ bits for ${\sf Rx}_{2}$ and in combination with
the available side-information $W_{2|1}$ with
$\left|W_{2|1}\right|=(1-\epsilon_{1})m$, ${\sf Rx}_{1}$ has sufficient
linearly independent equations to decode $W_{2}$ when the code length is large
enough.

Segment b: This segment has a total length of

$\displaystyle
t_{b}=\frac{(1-\delta_{1})-\epsilon_{1}(1-\delta_{2})}{(1-\delta_{1})(1-\delta_{2})}m=\frac{m}{(1-\delta_{2})}-t_{a}>0.$
(35)

During this segment, the transmitter creates $t_{b}$ random linear
combinations of the $\eta m$ bits in $W_{1}$, and creates the XOR of these
combinations with $t_{b}$ random combinations of the $m$-bit $W_{2}$ for ${\sf
Rx}_{2}$. The transmitter sends the resulting XORed sequence during Segment b.

The decodability comes as follows. In segment b, ${\sf Rx}_{1}$ can remove the
interference since $W_{2}$ is known from Segment a, and gets
$t_{b}(1-\delta_{1})=\eta m$ linearly independent equations for decoding
$W_{1}$ correctly. Also in this segment, ${\sf Rx}_{2}$ can remove the
interference from $W_{1}$ using the side-information $W_{1|2}=W_{1}$, then the
total linearly independent equations it has will be
$(t_{b}+t_{a})(1-\delta_{2})=m$. Thus, by the end of the communication block,
${\sf Rx}_{2}$ can decode $W_{2}$, and ${\sf Rx}_{1}$ can decode both $W_{1}$
and $W_{2}$.

Achievable rates: Since the total communication time is

$\displaystyle\frac{m}{(1-\delta_{2})},$ (36)

we immediately conclude the achievability of rates in (V).

Note that in the toy example aforementioned, only cache index information
$E^{nR_{1}}_{2}$ for $W_{1|2}=W_{1}$ is used at the transmitter in Segment b,
but not the other $E^{nR_{2}}_{1}(W_{2|1})$. Now we present the proof for the
general case $\epsilon_{2}\neq 0$ and show that the achievability also needs a
“semi-blind” transmitter. From (10), the non-trivial corner point of the
region defined in (8) is given by:

$\displaystyle
R_{1}=\frac{(1-\delta_{1})-\epsilon_{1}(1-\delta_{2})}{1-\frac{\epsilon_{1}\epsilon_{2}(1-\delta_{2})}{(1-\delta_{1})}},$
$\displaystyle
R_{2}=\frac{(1-\epsilon_{2})(1-\delta_{2})}{1-\frac{\epsilon_{1}\epsilon_{2}(1-\delta_{2})}{(1-\delta_{1})}}.$
(37)

We define

$\displaystyle\eta\overset{\triangle}{=}\frac{R_{1}}{R_{2}}=\frac{(1-\delta_{1})-\epsilon_{1}(1-\delta_{2})}{(1-\epsilon_{2})(1-\delta_{2})}.$
(38)

We note that if

$\displaystyle(1-\epsilon_{2}+\epsilon_{1})>\frac{(1-\delta_{1})}{(1-\delta_{2})},$
(39)

then $\eta<1$.

Achievability protocol for general $\epsilon_{2}$: We start with $m$ bits for
${\sf Rx}_{2}$ and $\eta m$ bits for ${\sf Rx}_{1}$. The achievability
protocol is carried over two phases with the first phase having two segments
as those for $\epsilon_{2}=0$. As revealed by the decodability in toy example,
the idea that after the first phase, receiver ${\sf Rx}_{2}$ (the weaker
receiver) decodes its message $W_{2}$. Since the first receiver has a stronger
channel, it can recover interference $W_{2}$ in a shorter time horizon after
the first segment of Phase I. Then, during the second segment of Phase I, the
transmitter starts delivering cached $W_{1|2}$ to ${\sf Rx}_{1}$, while it
continues delivering $W_{2}$ to ${\sf Rx}_{2}$. Note that since ${\sf Rx}_{2}$
knows $W_{1|2}$ and ${\sf Rx}_{1}$ has recovered $W_{2}$ in the first segment,
the second segment benefits both receivers. Finally, during the newly-added
second phase, $\bar{W}_{1|2}$ (the non-cached part of $W_{1}$ outside
$W_{1|2}$) is delivered to ${\sf Rx}_{1}$. The whole process is summarized in
Figure 6.

Figure 6: Semi-blind two-phase protocol to achieve outer-bounds
$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{NN}}$ in Theorem 1.

Phase I: The transmitter creates

$\displaystyle\frac{m}{(1-\delta_{2})}+O\left(m^{2/3}\right)$ (40)

random linear combinations of the $m$ bits intended for ${\sf Rx}_{2}$ such
that any randomly chosen $m$ combinations are randomly independent. This can
be accomplished by a random linear codebook of which each element is generated
from i.i.d. Bernoulli $\mathrm{Ber}(1/2)$. In practice, Fountain codes can be
used.

######  Remark 3 (Expected values of concentration results).

The $O\left(m^{2/3}\right)$ is to ensure sufficient number of equations will
be received given the stochastic nature of the channel. At the end we let
$m\rightarrow\infty$, such terms do not affect the achievability of the
overall rates. Thus, for simplicity of expressions, we omit these terms and
only work with the expected value of the number of equations in what follows,
since the actual number will converge to this expection.

Segment a of Phase I: This segment has a total (on average) length of $t_{a}$
as in (33). During this segment, the transmitter sends $t_{a}$ of the random
combinations it created for ${\sf Rx}_{2}$ as described above and illustrated
in Figure 6.

Segment b of Phase I: This segment has a total (on average) length of $t_{b}$
as (35). During this segment, the transmitter creates $t_{b}$ random linear
combinations of the $(1-\epsilon_{2})\eta m$ bits in $W_{1|2}$, and XORs these
combinations with the another $t_{b}$ random combinations it created for
$W_{2}$. The transmitter sends the XORed sequence during Segment b of Phase I.

Phase II: This phase has a total (on average) length of

$\displaystyle
t_{2}=\frac{\epsilon_{2}\left((1-\delta_{1})-\epsilon_{1}(1-\delta_{2})\right)}{(1-\epsilon_{2})(1-\delta_{1})(1-\delta_{2})}m=\frac{\epsilon_{2}\eta
m}{(1-\delta_{1})}.$ (41)

During this phase, the transmitter creates $t_{2}$ random linear combinations
of the bits in $\bar{W}_{1|2}$ and sends these combinations.

The decodability for ${\sf Rx}_{1}$ comes as follows. At the end of the second
phase, ${\sf Rx}_{1}$ gathers $\epsilon_{2}\eta m$ linearly independent
equations of non-cached $\bar{W}_{1|2}$, and as
$\left|\bar{W}_{1|2}\right|=\epsilon_{2}\eta m$, ${\sf Rx}_{1}$ can decode
$\bar{W}_{1|2}$. For cached $W_{1|2}$, as in toy example, during segment b of
Phase I, ${\sf Rx}_{1}$ can remove the interference ($W_{2}$ is known in
segment a) and decode $W_{1|2}$. Thus, ${\sf Rx}_{1}$ can decode ${W}_{1|2}$
and $\bar{W}_{1|2}$, meaning that it can recover $W_{1}$. The decodability for
${\sf Rx}_{2}$ after Phase I directly follows from that in the toy example.

Achievable rates: Recall the total length $t_{a}+t_{b}$ of Phase I is
$\frac{m}{(1-\delta_{2})}$ from (35), then with (41), the total communication
time is given by:

$\displaystyle
t_{a}+t_{b}+t_{2}=\frac{(1-\delta_{1})-\epsilon_{1}\epsilon_{2}(1-\delta_{2})}{(1-\epsilon_{2})(1-\delta_{1})(1-\delta_{2})}m,$
(42)

which immediately implies the achievability of rates in (V).

##  VI Achievability Proof for $\mathcal{C}^{\mathrm{blind}}_{\mathrm{DD}}$ in
Case A of Theorem 2

First, we remind the reader of the conditions in Case A of Theorem 2: global
delayed CSIT and symmetric channel where $\delta_{1}=\delta_{2}=\delta$ and
$\epsilon_{1}=\epsilon_{2}=\epsilon$. For this setup, we present an
opportunistic communication protocol that enables the transmitter to use the
available delayed CSI and the statistical knowledge of the available side-
information at the receivers. This protocol starts by sending the summation
(_i.e._ XOR in the binary field) of individual bits intended for the two
receivers, and then, based on the available channel feedback and the
statistics of receiver side-information, the transmitter is able to
efficiently create recycled bits for retransmission. In this regard, the
protocol has some similarities to the reverse Maddah-Ali-Tse scheme [26],
which was originally designed for multiple-input fading broadcast channels
[27]. As discussed in [28], the channel setting is fundamentally different:
discrete erasure channel vs. continuous Rayleigh channel, single antenna vs.
multiple-input transmitter. Together with the blind receiver side-information
in our case; thus, our protocols end up sharing little ingredients with [26].

We skip the protocol for achieving $R_{i}=\left(1-\delta\right)$, as it is a
well-established result. Instead, we provide the achievability protocol for
the maximum symmetric sum-rate point given by

$\displaystyle R_{1}=R_{2}=\frac{1-\delta^{2}}{1+\delta+\epsilon}.$ (43)

Figure 7: The proposed four-phase protocol when $\epsilon\leq\delta$: Phase I
delivers combinations of $\vec{a}$ and $\vec{b}$; Phases II and III deliver
interfering bits to unintended receivers alongside useful information to the
intended receivers; Phase IV multicasts XOR of available bits at each receiver
needed at the other.

We break the scheme based on the relationship between $\epsilon$ and $\delta$.
We note that since we focus on the homogeneous setting in this section, the
transmitter has $m$ bits for each receiver: $a_{j}$’s for receiver ${\sf
Rx}_{1}$ and $b_{j}$’s for receiver ${\sf Rx}_{2}$, $j=1,2,\ldots,m$.

Scenario 1 ($\epsilon\leq\delta$): This case assumes the side channel that
provides each receiver its side-information is stronger than the channel from
the transmitter. The transmitter first creates
$\vec{c}=\left(c_{1},c_{2},\ldots,c_{m}\right)$ according to

$\displaystyle c_{j}=a_{j}\oplus b_{j},\qquad j=1,2,\ldots,m.$ (44)

The protocol is divided into four phases as described below and depicted in
Figure 7.
Phase I: During this phase, the transmitter sends out individual bits from
$\vec{c}$ until at least one receiver obtains this bit, and then, moves on to
the next bit. Due to the statistics of the channel, this phase takes on
average

$\displaystyle t_{1}=\frac{m}{1-\delta^{2}}$ (45)

time instants.

######  Remark 4.

To keep the description of the protocol simple, we use the expected value of
different random variable (_e.g._ length of phase, number of bits received by
each user, etc). A more precise statement would use a concentration theorem
result such as the Bernstein inequality to show the omitted terms do not
affect the overall result and the achievable rates as done in [29, 30].
Moreover, when talking about the number of bits or time instants, we are
limited to integer numbers. If a ratio is not an integer number, we can use
$\lceil\cdot\rceil$, the ceiling function, and since at the end we take the
limit for $m\rightarrow\infty$, the results remain unchanged.

After Phase I is completed, receiver $\mathsf{Rx}_{1}$ obtains on average
$m/(1+\delta)$ bits from $\vec{c}$. The transmitter, using channel feedback
during Phase I, knows which bits out of $\vec{b}$ where among those received
by $\mathsf{Rx}_{1}$ as part of $\vec{c}$, denoted by $\vec{\tilde{b}}$ in
Figure 7. Furthermore, $\mathsf{Rx}_{1}$ statistically knows a fraction
$(1-\epsilon)$ of the interfering $\vec{\tilde{b}}$ from its side-information.
Thus, if $\mathsf{Rx}_{1}$ obtains an additional fraction $\epsilon$ of
$\vec{\tilde{b}}$, it can resolve interference in Phase I to get
$m/(1+\delta)$ pure bits from $\vec{a}$. A similar statement holds for
$\mathsf{Rx}_{2}$.

Phase II: The transmitter creates $\epsilon m/(1+\delta)$ linearly independent
combinations of $\vec{\tilde{b}}$, and encodes them using an erasure code of
rate $(1-\delta)$ and sends them out. This phase takes

$\displaystyle t_{2}=\frac{\epsilon m}{1-\delta^{2}},$ (46)

time instant, and upon its completion, $\mathsf{Rx}_{1}$ gets the additional
equations to remove interference during Phase I and recover $m/(1+\delta)$
bits from $\vec{a}$, while $\mathsf{Rx}_{2}$ obtains further $\epsilon
m/(1+\delta)$ equations of its intended bits.

Phase III: This phase is similar to Phase II, but the transmitter sends out
$\vec{\tilde{a}},$ those bits out of $\vec{a}$ that were received by
$\mathsf{Rx}_{2}$ as part of $\vec{c}$. This phase takes

$\displaystyle t_{3}=\frac{\epsilon m}{1-\delta^{2}},$ (47)

time instants, and upon its completion, $\mathsf{Rx}_{2}$ gets the additional
equations to remove interference during Phase I and recover $m/(1+\delta)$
bits from $\vec{b}$, while $\mathsf{Rx}_{1}$ obtains further $\epsilon
m/(1+\delta)$ equations of its intended bits.

Number of equations at each receiver: After the first three phases, each
receiver has a total of

$\displaystyle\frac{m}{1+\delta}+\frac{\epsilon m}{1+\delta}$ (48)

linearly independent equations of its bits, and thus, needs an additional

$\displaystyle\frac{\delta-\epsilon}{1+\delta}m$ (49)

new equations to complete recovery of its bits. Note that if
$\epsilon=\delta$, the protocol ends here.

Phase IV: The transmitter creates

$\displaystyle\frac{\delta-\epsilon}{1+\delta}m$ (50)

further linearly independent random combinations of the bits intended for
$\mathsf{Rx}_{i}$ but received at $\mathsf{Rx}_{\bar{i}}$ as part of $\vec{c}$
during Phase I, denoted by $\vec{\tilde{a}}$ and $\vec{\tilde{b}}$ in Figure
7. Note that at this point, each receiver has full knowledge of the
interfering bits during Phase I and retransmission of such bits will no longer
create any interference. Thus, the transmitter encodes these two sets of bits
(one for each receiver) using an erasure code of rate $\left(1-\delta\right)$
and send the XOR of these encoded bits. This phase takes

$\displaystyle t_{4}=\frac{\delta-\epsilon}{1-\delta^{2}}m$ (51)

time instants.

We note that in Phases II, III, and IV, the transmitter needs to create
linearly independent combinations of the bits. Thus, we need to guarantee the
feasibility of these operations. In Phase I, as part of $\vec{c}$, a total of

$\displaystyle\frac{\delta}{1+\delta}m$ (52)

bits intended for one receiver arrive at the unintended receiver and
effectively, during the next phases, we deliver these bits to the intended
receiver. In fact, (52) equals the summation of the number of linearly
equations needed for $\mathsf{Rx}_{1}$ during Phases III and IV, and for
$\mathsf{Rx}_{2}$ during Phases II and IV. Thus, the feasibility of creating
sufficient number of linearly independent combinations is guaranteed.

Upon completion of Phase IV, each receiver first removes the contribution of
the bits intended for the other user, and then, recovers the additional
equations needed as indicated in (49), and thus, is able to complete recovery
of its message.

Achievable rates: The total communication time is

$\displaystyle\sum_{j=1}^{4}{t_{j}}=\frac{1+\delta+\epsilon}{1-\delta^{2}}m,$
(53)

which immediately results in target rates of (43).

Scenario 2 ($\epsilon>\delta$): This scenario corresponds to the case in which
the side channel that provides each receiver with its side-information is
weaker than the channel from the transmitter. The protocol has four phases as
before with some modifications. Phase I remains identical to the previous
scenario; during Phases II and III, instead of $\epsilon m/(1+\delta)$, the
transmitter creates $\delta m/(1+\delta)$ linearly independent equations of
$\vec{\tilde{b}}$ and $\vec{\tilde{a}}$, respectively, and sends them out as
done in the previous scenario. With these modifications, after the first three
phases, $\mathsf{Rx}_{1}$, still has

$\displaystyle\frac{\epsilon-\delta}{1+\delta}m$ (54)

equations interfered by $\vec{\tilde{b}}$. Thus, for $\mathsf{Rx}_{1}$ to
successfully recover $\vec{a}$, the transmitter has two options: $(i)$ to
deliver the same number as in $\eqref{Eq:Sc2AfterPh12}$, new combinations of
$\vec{\tilde{b}}$ to $\mathsf{Rx}_{1}$, and $(ii)$ to provide
$\mathsf{Rx}_{1}$ with additional combinations, same as in
$\eqref{Eq:Sc2AfterPh12}$ , of its own bits $\vec{\tilde{a}}$. With the first
choice, receiver $\mathsf{Rx}_{1}$ fully resolves the interference and
recovers its bits; while with the second choice, it simply obtains $m$
linearly independent equations of $\vec{a}$. Interestingly, either choice is
also good for $\mathsf{Rx}_{2}$: with the first choice, $\mathsf{Rx}_{2}$
obtains $m$ linearly independent equations of $\vec{b}$; while with the first
choice, $\mathsf{Rx}_{2}$ fully resolves the interference and recovers its
bits. In other words, in this scenario, during Phase IV, no XOR operation is
needed and only bits intended for one user would enable both receivers to
decode their bits.

Based on the discussion above, during Phase IV, the transmitter creates
$\left(\epsilon-\delta\right)/\left(1+\delta\right)m$ linearly independent
combinations, same as (54), of the bits in $\vec{\tilde{a}}$ intended for
$\mathsf{Rx}_{1}$ but received as part of $\vec{c}$ at $\mathsf{Rx}_{2}$
during Phase I. Then, the transmitter encodes these equations using an erasure
code of rate $\left(1-\delta\right)$ and sends them to both receivers. Similar
to the previous scenario, we can guarantee the feasibility of creating these
linearly independent equations.

After Phase IV, as discussed above, $\mathsf{Rx}_{1}$ will have sufficient
number of equations to recover $\vec{a}$; while $\mathsf{Rx}_{2}$ first needs
to resolve the interference using the equations it obtains during this phase,
and then, recover $\vec{b}$. We note that, the transmitter could send
combinations of $\vec{b}$ instead of $\vec{a}$ during the last phase, and the
decoding strategy of the receivers would get swapped.

##  VII Achievability Proofs for $\mathcal{C}^{\mathrm{semi-
blind}}_{\mathrm{DN}}$ in Case B and
$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{DN}}$ in Case C of Theorem 2

Case B : Achievability for $\mathcal{C}^{\mathrm{semi-blind}}_{\mathrm{DN}}$
when $\epsilon_{1}=0$ : Now $\epsilon_{1}=0$ and thus $W_{2|1}=W_{2}$. Recall
message $W_{2}$ is also represented by a bit vector $\vec{b}$. The encoding
process come as follows. At time index $t$, the $j$-th bit $a_{j}$ in message
$\vec{a}$ for $\mathsf{Rx}_{1}$ is repeated according to the state feedback
$S_{1}$, and after XORing a random linear combination
$(\vec{g}_{t})^{\intercal}\vec{b}$, the resulting superposition is sent. Each
entry of $\vec{g}_{t}$ is generated from $i.i.d.$ $\mathrm{Ber}(1/2)$. Each
$a_{j}$ is repeated until the corresponding state feedback is $S_{1}=1$. In
other words, prior to the superposition via XORing, $\vec{a}$ is pre-encoded
and repeated as in standard ARQ, while $\vec{b}$ is pre-encoded by a fountain-
like random linear code. the termination of this fountain code is determined
by the state feedback of $\mathsf{Rx}1$, that is whether or not all bits in
$\vec{a}$ are successfully delivered to $\mathsf{Rx}1$.

The decoding at $\mathsf{Rx}_{1}$ follows from the standard ARQ, since full
side-information $\vec{b}$ is known. By setting total transmission length as

$\frac{m_{1}}{1-\delta_{1}},$ (55)

the achievable rate is

$R_{1}=1-\delta_{1}$ (56)

For user $\mathsf{Rx}_{2}$, it has side-information $W_{1|2}$ for
$(1-\epsilon_{2})$ bits of the interference $\vec{a}$ and each reception of
the corresponding XOR transmitted will result in a linear equation of
$\vec{b}$. To see this, consider the $j$-th bit $a_{j}$ of interference
$\vec{a}$. Suppose it is repeated $L_{i}$ times until its mixture with
$\vec{b}$ is successfully arrived at $\mathsf{Rx}1$. Within this span,
$\mathsf{Rx}2$ gets

$K_{i}\triangleq\sum_{\ell=1}^{L_{j}}S_{2,j}[\ell]$ (57)

linear equations mixing $a_{j}$ and $\vec{b}$, where $S_{2,j}[\ell]$ is the
erasure state at $\mathsf{Rx}2$ for the $\ell$-th transmission of $a_{j}$.
Then $\mathsf{Rx}2$ gets $K_{i}$ pure equations of $\vec{b}$. In total, the
number of pure linear equations of message $\vec{b}$ is

$m_{1}(1-\epsilon_{2})\mathbb{E}[K_{i}]=m_{1}(1-\epsilon_{2})\frac{1-\delta_{2}}{1-\delta_{1}},$
(58)

For interference bits without side-information, by using interference
alignment in [12], the number of pure linear equations is

$m_{1}\epsilon_{2}\mathbb{E}[(K_{i}-1)^{+}]=m_{1}\epsilon_{2}\left(\frac{\delta_{1}-\delta_{2}}{1-\delta_{1}}+\frac{\delta_{2}-\delta_{1}\delta_{2}}{1-\delta_{1}\delta_{2}}\right)$
(59)

Thus the total number of pure equations from (58) and (59) is

$m_{1}(1-\delta_{2})\left(\frac{1}{1-\delta_{1}}-\frac{\epsilon_{2}}{1-\delta_{1}\delta_{2}}\right),$

which results in achievable rate

$R_{2}=(1-\delta_{2})\left(1-\epsilon_{2}\frac{1-\delta_{1}}{1-\delta_{1}\delta_{2}}\right)$
(60)

where (55) is applied. It can be checked that $(R_{1},R_{2})$ in (56)(60) is
the corner point of outer-bound region (12) when $\epsilon_{1}=0$

$\displaystyle\epsilon_{2}\frac{1-\delta_{2}}{1-\delta_{1}\delta_{2}}$
$\displaystyle R_{1}+R_{2}\leq\left(1-\delta_{2}\right)$ (61) $\displaystyle
0\leq$ $\displaystyle R_{i}\leq(1-\delta_{i}),i=1,2,$ (62)

Other corner point can be trivially achieved by time-sharing.

Figure 8: Proposed four-phase protocol for achieving
$\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{DN}}$.

Case C : Achievability for $\mathcal{C}^{\mathrm{non-blind}}_{\mathrm{DN}}$ :
As in Fig. 8, we now introduce the four-phase scheme for this achievability,
of which the third and fourth phases are similar to that in Case B. We first
represent $W_{2|1}$ and $W_{1|2}$ using bit vectors $\vec{b}_{1}$ and
$\vec{a}_{2}$ respectively, then the encoding process is
Phase I : The transmitter sends bits from $\vec{a}$ which are not cached at
$\mathsf{Rx}_{2}$ and not in $\vec{a}_{2}$. The total length $t_{1}$ of Phase
I is $\epsilon_{2}m_{1}$. After Phase I, the transmitter knows length
$t_{1}\delta_{1}$ sequence $\bar{\tilde{a}}_{2}$, which is formed by bits
erased at $\mathsf{Rx}1$ in Phase I where $S_{1}[t]=0$.

Phase II : The transmitter selects $\epsilon_{1}m_{2}$ bits from $\vec{b}$
which are not cached at $\mathsf{Rx}_{1}$ and not in $\vec{b}_{1}$, and send
then random linear combinations of them. The total length $t_{2}$ of Phase II
is $\epsilon_{1}m_{2}/(1-\delta_{1}\delta_{2})$. After Phase II, the
transmitter knows length $t_{2}(1-\delta_{1})$ sequence $\bar{\tilde{b}}_{1}$,
which is formed by bits received at $\mathsf{Rx}1$ in Phase I where
$S_{1}[t]=1$.

Phase III : The transmission is similar to that in semi-blind Case B, the
differences are as follows. Now the transmitter is non-blind to $\vec{a}$ so
it pre-encodes cached $\vec{a}_{2}$ instead of the whole $\vec{a}$ using ARQ.
Also the transmitter is only sure that $(\bar{\tilde{b}}_{1},\vec{b}_{1})$ is
known at $\mathsf{Rx}_{1}$, it pre-encodes $(\bar{\tilde{b}}_{1},\vec{b}_{1})$
instead of full $\vec{b}$ using the random linear code. More specifically, the
output of the second pre-encoder at time $t$ becomes the XOR of random linear
combinations
$(\vec{g}_{t})^{\intercal}\bar{\tilde{b}}_{1}\oplus(\vec{g^{\prime}}_{t})^{\intercal}\vec{b}_{1}$,
where each entry of $\vec{g}_{t}$ or $\vec{g^{\prime}}_{t}$ is generated from
i.i.d. $\mathrm{Ber}(1/2).$ For the first pre-encoder, each bit in
$\vec{a}_{2}$ cached at user 2 is repeated according to the delayed $S_{1}$ as
described in Case B. Finally the XOR of outputs of these two pre-encoders is
sent.

Phase IV: The transmission in phase is same as that in Phase III, by replacing
the input of the first ARQ pre-encoder by the recycled $\bar{\tilde{a}}_{2}$.
Though $(1-\delta_{2})$ of sequence $\bar{\tilde{a}}_{2}$ will be known at
$\mathsf{Rx}_{2}$ in Phase IV, the transmitter is blind to these bits. On the
contrary, in Phase III the transmitter knows that the input $\vec{a}_{2}$ of
the ARQ pre-encoder is totally cached at $\mathsf{Rx}_{2}$.

Note that without receiver side-information $\epsilon_{1}=\epsilon_{2}=1$,
there will be no Phase III and our scheme reduces to the three-phase scheme in
[12].

We focus on the decodability for receiver $\mathsf{Rx}1$ first. In Phase III
and IV, since $(\bar{\tilde{b}}_{1},\vec{b}_{1})$ is already known at
$\mathsf{Rx}_{1}$, $\vec{a}_{2}$ and $\bar{\tilde{a}}_{2}$ can be recovered,
if the lengthes of Phases are respectively chosen as

$\displaystyle t_{3}(1-\delta_{1})=(1-\epsilon_{2})m_{1}$ $\displaystyle
t_{4}(1-\delta_{1})=\delta_{1}t_{1}=\delta_{1}\epsilon_{2}m_{1}$ (63)

Together with bits received in Phase I, receiver $\mathsf{Rx}1$ gets all
$m_{1}$ bits. Now, we turn to the decodability at $\mathsf{Rx}2$. Receiver
$\mathsf{Rx}2$ will first decode super-$(\bar{\tilde{b}}_{1},\vec{b}_{1})$
from its received bits during the entire three phases. With the
$\bar{\tilde{b}}_{1}$ and the received equations during Phase II, it will have
$t_{2}(1-\delta_{1}\delta_{2})=\epsilon_{1}m_{2}$ equations to decode uncached
bits in $\vec{b}$. Together with $\vec{b}_{1}$, the whole message for user 2
is decoded. To ensure successful decoding of the
super-$(\bar{\tilde{b}}_{1},\vec{b}_{1})$, we calculate the corresponding
expected number of linearly independent equations as follows. In Phase III,
every reception at $\mathsf{Rx}_{2}$ will result in a new equation since
$\vec{a}_{2}$ is cached, and we have

$(1-\epsilon_{2})m_{1}\mathbb{E}[K_{i}]$

equations after Phase III. In Phase IV, as (58) and (59), we will have
additional

$t_{1}\delta_{1}(1-\delta_{2})\mathbb{E}[K_{i}]+t_{1}\delta_{1}\delta_{2}\mathbb{E}[(K_{i}-1)^{+}]$

equations since $(1-\delta_{2})$ of $\bar{\tilde{a}}_{2}$ will be received
during Phase I. By using equations of $\bar{\tilde{b}}_{1}$ received at
$\mathsf{Rx}_{2}$ in Phase II as additional cache, we need

$\displaystyle t_{2}(1-\delta_{1})+(1-\epsilon_{1})m_{2}\leq$ $\displaystyle
t_{2}(1-\delta_{1}-\delta_{2}+\delta_{1}\delta_{2})+(1-\epsilon_{2})m_{1}\frac{1-\delta_{2}}{1-\delta_{1}}+t_{1}\delta_{1}(1-\delta_{2})\left(\frac{1}{1-\delta_{1}}-\frac{\delta_{2}}{1-\delta_{1}\delta_{2}}\right)$
(64)

for successful decoding the length $t_{2}(1-\delta_{1})+(1-\epsilon_{1})m_{2}$
super-$(\bar{\tilde{b}}_{1},\vec{b}_{1})$. Note that by collecting
$\bar{\tilde{b}}_{1}$ received in Phase II (with standard basis for
$\bar{\tilde{b}}_{1}$) and the linear equations produced in Phase III and IV,
one can form a set of linear equations of $(\bar{\tilde{b}}_{1},\vec{b}_{1})$
described by a full (column) rank matrix, when codelengths are long enough.

For $(R_{1},R_{2})$ satisfying outer-bound
$R_{1}/(1-\delta_{1})+\epsilon_{1}R_{2}/(1-\delta_{1}\delta_{2})=1$ in (12),
the total communication time must meet

$\sum^{4}_{j=1}t_{j}=\frac{m_{1}}{1-\delta_{1}}+\frac{\epsilon_{1}m_{2}}{1-\delta_{1}\delta_{2}}.$

From selected lengths of Phase I and II, $m_{1}=t_{1}/\epsilon_{2}$ and
$m_{2}=t_{2}(1-\delta_{1}\delta_{2})/\epsilon_{1}$, together with (63), this
constraint is meet since

$\sum^{4}_{j=1}t_{j}=t_{1}\left(1+\frac{(1-\epsilon_{2})/\epsilon_{2}+\delta_{1}}{1-\delta_{1}}\right)+t_{2}=\frac{t_{1}}{\epsilon_{2}(1-\delta_{1})}+t_{2}$

For the corner point $(R_{1},R_{2})$ which also satisfies outer-bound
$R_{2}/(1-\delta_{2})+\epsilon_{2}R_{1}/(1-\delta_{1}\delta_{2})=1$ in (12),
we further show that the decodability (64) will also be met. From (12),

$\frac{t_{1}}{1-\delta_{1}\delta_{2}}+\frac{1-\delta_{1}\delta_{2}}{\epsilon_{1}(1-\delta_{2})}t_{2}=\sum^{4}_{j=1}t_{j}=\frac{t_{1}}{\epsilon_{2}(1-\delta_{1})}+t_{2},$

which implies

$t_{2}\left(\frac{1-\delta_{1}\delta_{2}}{\epsilon_{1}}-(1-\delta_{2})\right)=t_{1}(1-\delta_{2})\left(\frac{1}{\epsilon_{2}(1-\delta_{1})}-\frac{1}{1-\delta_{1}\delta_{2}}\right),$

or equivalently

$t_{2}\left(\delta_{2}-\delta_{1}\delta_{2}+\frac{1-\epsilon_{1}}{\epsilon_{1}}(1-\delta_{1}\delta_{2})\right)=t_{1}(1-\delta_{2})\left(\frac{(1-\epsilon_{2})/\epsilon_{2}}{1-\delta_{1}}+\left(\frac{1}{1-\delta_{1}}-1\right)-\left(\frac{1}{1-\delta_{1}\delta_{2}}-1\right)\right).$

Then (64) is met since $m_{1}=t_{1}/\epsilon_{2}$ and
$m_{2}=t_{2}(1-\delta_{1}\delta_{2})/\epsilon_{1}$.

##  VIII Conclusion

We studied the problem of communications over two-user broadcast erasure
channels with random receiver side-information. We assumed the transmitter may
not have access to global channel state information and global cache index
information for both receivers. For the non-blind-transmitter case, we
characterized the capacity region, while with a blind transmitter we showed
the outer-bounds can be achieved under certain conditions. Thus, in general
with a blind transmitter, the capacity region of the problem, also known as
blind index coding over the broadcast erasure channel, remains open.

##  Appendix A Proof of (25) in Lemma 2

For time instant $t$ where $2\leq t\leq n$, we have

$\displaystyle
H\left(Y_{2}[t]|Y_{2}^{t-1},W_{1|2},W_{2},S_{2}^{t},E^{n}\right)$ (65)
$\displaystyle\quad=\left(1-\delta_{2}\right)H\left(X[t]|Y_{2}^{t-1},W_{1|2},W_{2},S_{2}[t]=1,S_{2}^{t-1},E^{n}\right)$
$\displaystyle\quad\overset{(a)}{=}\left(1-\delta_{2}\right)H\left(X[t]|Y_{2}^{t-1},W_{1|2},W_{2},S_{2}^{t},E^{n}\right)$
$\displaystyle\quad\overset{(b)}{\geq}\left(1-\delta_{2}\right)H\left(X[t]|Y_{1}^{t-1},W_{1|2},W_{2},S_{1}^{t},E^{n}\right)$
$\displaystyle\quad\overset{(c)}{=}\frac{1-\delta_{2}}{1-\delta_{1}}H\left(Y_{1}[t]|Y_{1}^{t-1},W_{1|2},W_{2},S_{1}^{t},E^{n}\right),$
(66)

where $(a)$ holds since $X[t]$ is independent of the channel realization at
time instant $t$; $(b)$ follows from the following arguments. Consider a
virtual channel state $\tilde{S}[t]$ is an i.i.d. Bernoulli
$(\delta_{2}-\delta_{1})/\delta_{2}$ process independent of $S_{2}[t]$ and
transmitted signal, then, we have

$\displaystyle H\left(X[t]|Y_{2}^{t-1},W_{1|2},W_{2},S_{2}^{t},E^{n}\right)$
$\displaystyle=H\left(X[t]|Y_{2}^{t-1},W_{1|2},W_{2},S_{2}^{t},\tilde{S}^{t-1},E^{n}\right)$
$\displaystyle\geq
H\left(X[t]|\\{(1-S_{2}[\ell])\tilde{S}[\ell]X[\ell]\\}_{\ell=1}^{\ell=t-1},Y_{2}^{t-1},W_{1|2},W_{2},S_{2}^{t},\tilde{S}^{t-1},E^{n}\right)$
$\displaystyle=H\left(X[t]|Y_{1}^{t-1},W_{1|2},W_{2},S_{1}^{t},E^{n}\right),$
(67)

where the third equality holds since receiving both virtual
$(1-S_{2}[\ell])\tilde{S}[\ell]X[\ell]$ and $Y_{2}[\ell]=S_{2}[\ell]X[\ell]$
is statistically the same as receiving $S_{1}[\ell]X[\ell]=Y_{1}[\ell]$ (note
if $S_{2}[\ell]=0$ there is $(\delta_{2}-\delta_{1})/\delta_{2}$ probability
$(1-S_{2}[\ell])\tilde{S}[\ell]=1$), and $X[t]$ is independent of the channel
states and virtual $\tilde{S}^{t-1}$; $(c)$ comes from the fact that
$\Pr\left(S_{1}[t]=0\right)=\delta_{1}$. Next, taking the summation over $t$
from $1$ to $n$, and using the fact that the transmit signal at time instant
$t$ is independent of future channel realizations, we get

$H\left(Y_{2}^{n}|W_{1|2},W_{2},S^{n}_{2},E^{n}\right)\geq\frac{1-\delta_{2}}{1-\delta_{1}}H\left(Y_{1}^{n}|W_{1|2},W_{2},S^{n}_{1},E^{n}\right)$

and also (25).

##  Appendix B Proof of $\mathcal{C}^{\mathrm{blind}}_{\mathrm{NN}}$ in
Theorem 3: Opportunistic Transmission

Case 1 : $\delta_{2}\geq\delta_{1}$ and $\epsilon_{2}\in\\{0,1\\}$: First, we
note that as stated in Remark 2, when the weaker receiver has no side-
information, _i.e._ $\epsilon_{2}=1$, then, the capacity region is the same as
having no side-information at either receivers. The case with $\epsilon_{2}=0$
is already given in Section V

Case 2 : $\delta_{1}=\delta_{2}=\delta$, and
$\epsilon_{1}=\epsilon_{2}=\epsilon$ (symmetric setting):

Now we focus on the blind-transmitter assumption where the transmitter no
longer has the luxury of knowing $W_{1|2}$ to send bits in such a way to
benefit both receivers (as was done in Segment b of Phase I in the previous
section V). We note that if both $\epsilon_{1}$ and $\epsilon_{2}$ are equal
to zero, the problem becomes trivial as each receiver has full side-
information of the other user’s message and $R_{i}=(1-\delta_{i})$ is
achievable for $i=1,2$. For case $\epsilon_{1}=\epsilon_{2}=\epsilon>0$, if
each receiver obtains a total of $(1+\epsilon)m$ linearly independent
observation of both $W_{1}$ and $W_{2}$, then, it can recover both messages.
It turns out that this protocol is capacity-achieving. The non-trivial corner
point in this case is given by:

$\displaystyle R_{1}=R_{2}=\frac{(1-\delta)}{(1+\epsilon)}.$ (68)

The protocol is straightforward. The transmitter starts with $m$ bits for each
receiver and creates $(1+\epsilon)m$ linearly independent combinations of the
total $2m$ bits for the two receivers. Then, the transmitter encodes these
combinations using an erasure code of rate $(1-\delta)$ and communicates the
encoded message. Each receiver by the end of the communication block will have
$2m$ linearly independent observations of the $2m$ unknown variables and can
decode both messages. This immediately implies the achievability of the corner
point described in (68).

##  Appendix C Proof of Theorem 4

In this case, receiver ${\sf Rx}_{1}$ (the stronger receiver) has full side-
information of the message for ${\sf Rx}_{2}$, _i.e._ $W_{2|1}=W_{2}$, and
receiver ${\sf Rx}_{2}$ has access to $(1-\epsilon_{2})$ of the bits intended
for ${\sf Rx}_{1}$. The outer-bounds of Theorem 1 in this case become:

$\left\\{\begin{array}[]{ll}0\leq\epsilon_{2}\frac{1-\delta_{2}}{1-\delta_{1}}R_{1}+R_{2}\leq\left(1-\delta_{2}\right),&\\\
0\leq R_{1}\leq\left(1-\delta_{1}\right).\end{array}\right.$ (69)

Thus, the non-trivial corner point is given by:

$\displaystyle R_{1}=(1-\delta_{1}),$ $\displaystyle
R_{2}=(1-\epsilon_{2})(1-\delta_{2}).$ (70)

In this case. we cannot achieve the corner point given in (C). To achieve the
region described in Theorem 4, we need to prove the achievability of the
following corner point:

$\displaystyle R_{1}=(1-\delta_{1}),$ $\displaystyle
R_{2}=(1-\epsilon_{2})(1-\delta_{1})(1-\delta_{2}).$ (71)

Achievability protocol: We start with $m$ bits for ${\sf Rx}_{2}$ and $\eta m$
bits for ${\sf Rx}_{1}$, where

$\displaystyle\eta=\frac{R_{1}}{R_{2}}=\frac{1}{(1-\epsilon_{2})(1-\delta_{2})}>1.$
(72)

The achievability protocol is carried over two phases. During the first phase,
the transmitter creates $\eta m$ random linear combinations of the $m$ bits
for ${\sf Rx}_{2}$ such that each subset of $m$ combinations are linearly
independent. The transmitter then sends out the XOR of these combinations with
the uncoded $\eta m$ bits of ${\sf Rx}_{1}$. Thus, this phase has a length of

$\displaystyle t_{1}=\eta m.$ (73)

During this phase, ${\sf Rx}_{1}$ obtains $(1-\delta_{1})\eta m$ of its bits
as it has access to $W_{2}$ as side-information and can cancel out the
interference. Moreover, ${\sf Rx}_{2}$ obtains $(1-\delta_{2})\eta m$ XORed
combinations, and since ${\sf Rx}_{2}$ statistically knows $(1-\epsilon_{2})$
of the bits for ${\sf Rx}_{1}$, we conclude that ${\sf Rx}_{2}$ gathers

$\displaystyle(1-\epsilon_{2})(1-\delta_{2})\eta m=m$ (74)

linearly independent combinations of its $m$ bits and is able to decode its
message $W_{2}$.

The second phase has a total length of

$\displaystyle t_{2}=\frac{\delta_{1}}{(1-\delta_{1})}\eta m.$ (75)

During this second phase, the transmitter creates $t_{2}$ random linear
combinations of the $\eta m$ bits intended for ${\sf Rx}_{1}$ and sends them
out. At the end of this phase, the first receiver gathers additional
$(1-\delta_{1})\eta m$ random equations of its intended bits and combined with
the $(1-\delta_{1})\eta m$ bits it already knows from the first phase, ${\sf
Rx}_{1}$ is able to decode $W_{1}$.

Achievable rates: The total communication time is

$\displaystyle t_{1}+t_{2}=\frac{\eta m}{(1-\delta_{1})}.$ (76)

This immediately implies the achievability of the rates given in (C).

## References

  * [1] M. A. Maddah-Ali and U. Niesen, “Cache-aided interference channels,” in 2015 IEEE International Symposium on Information Theory (ISIT), pp. 809–813, IEEE, 2015.
  * [2] N. Naderializadeh, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental limits of cache-aided interference management,” IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 3092–3107, 2017.
  * [3] S. Prakash, A. Reisizadeh, R. Pedarsani, and S. Avestimehr, “Coded computing for distributed graph analytics,” in 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1221–1225, IEEE, 2018.
  * [4] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” in Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 41–50, IEEE, 1995.
  * [5] H. Sun and S. A. Jafar, “Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by freij-hollanti et al.,” IEEE Transactions on Information Theory, vol. 64, no. 2, pp. 1000–1022, 2017.
  * [6] Z. Bar-Yossef, Y. Birk, T. Jayram, and T. Kol, “Index coding with side information,” IEEE Transactions on Information Theory, vol. 57, no. 3, pp. 1479–1494, 2011.
  * [7] M. A. R. Chaudhry and A. Sprintson, “Efficient algorithms for index coding,” in IEEE INFOCOM Workshops 2008, pp. 1–4, IEEE, 2008.
  * [8] H. Maleki, V. R. Cadambe, and S. A. Jafar, “Index coding–An interference alignment perspective,” IEEE Transactions on Information Theory, vol. 60, no. 9, pp. 5402–5432, 2014.
  * [9] D. T. Kao, M. A. Maddah-Ali, and A. S. Avestimehr, “Blind index coding,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2076–2097, 2016\.
  * [10] A. Ghorbel, M. Kobayashi, and S. Yang, “Content delivery in erasure broadcast channels with cache and feedback,” IEEE Transactions on Information Theory, vol. 62, no. 11, pp. 6407–6422, 2016.
  * [11] M. Zohdy, A. Tajer, and S. Shamai, “Distributed interference management: A broadcast approach,” IEEE Transactions on Communications, vol. 69, no. 1, pp. 149–163, 2021.
  * [12] S.-C. Lin, I.-H. Wang, and A. Vahid, “No feedback, no problem: Capacity of erasure broadcast channels with single-user delayed CSI,” in IEEE International Symposium on Information Theory (ISIT), pp. 1647–1651, IEEE, 2019\.
  * [13] A. Vahid, I.-H. Wang, and S.-C. Lin, “Capacity results for erasure broadcast channels with intermittent feedback,” in IEEE Information Theory Workshop (ITW), pp. 1–5, IEEE, 2019.
  * [14] C. Karakus, I.-H. Wang, and S. Diggavi, “Gaussian interference channel with intermittent feedback,” IEEE Transactions on Information Theory, vol. 61, no. 9, pp. 4663–4699, 2015.
  * [15] Q. Liu, J. Guo, C.-K. Wen, and S. Jin, “Adversarial attack on DL-based massive MIMO CSI feedback,” arXiv preprint arXiv:2002.09896, 2020.
  * [16] M. Sadeghi and E. G. Larsson, “Adversarial attacks on deep-learning based radio signal classification,” IEEE Wireless Communications Letters, vol. 8, no. 1, pp. 213–216, 2018.
  * [17] M. Sadeghi and E. G. Larsson, “Physical adversarial attacks against end-to-end autoencoder communication systems,” IEEE Communications Letters, vol. 23, no. 5, pp. 847–850, 2019.
  * [18] Y. Birk and T. Kol, “Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clients,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2825–2830, 2006\.
  * [19] N. Alon, E. Lubetzky, U. Stav, A. Weinstein, and A. Hassidim, “Broadcasting with side information,” in 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 823–832, IEEE, 2008.
  * [20] L. Ong, “Linear codes are optimal for index-coding instances with five or fewer receivers,” in 2014 IEEE International Symposium on Information Theory, pp. 491–495, IEEE, 2014.
  * [21] S. A. Jafar, “Topological interference management through index coding,” IEEE Transactions on Information Theory, vol. 60, no. 1, pp. 529–568, 2013.
  * [22] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867, 2014.
  * [23] A. Vahid, M. A. Maddah-Ali, and A. S. Avestimehr, “Communication through collisions: Opportunistic utilization of past receptions,” in Proceedings INFOCOM, pp. 2553–2561, IEEE, 2014.
  * [24] M. Gatzianas, L. Georgiadis, and L. Tassiulas, “Multiuser broadcast erasure channel with feedback – capacity and algorithms,” IEEE Transactions on Information Theory, vol. 59, no. 9, pp. 5779–5804, 2013.
  * [25] A. Vahid, M. A. Maddah-Ali, and A. S. Avestimehr, “Capacity results for binary fading interference channels with delayed CSIT,” IEEE Transactions on Information Theory, vol. 60, pp. 6093–6130, Oct. 2014.
  * [26] S. Yang, M. Kobayashi, D. Gesbert, and X. Yi, “Degrees of freedom of time correlated MISO broadcast channel with delayed CSIT,” IEEE transactions on information theory, vol. 59, no. 1, pp. 315–328, 2012.
  * [27] M. A. Maddah-Ali and D. Tse, “Completely stale transmitter channel state information is still very useful,” IEEE Transactions on Information Theory, vol. 58, no. 7, pp. 4418–4431, 2012.
  * [28] S.-C. Lin and I.-H. Wang, “Gaussian broadcast channels with intermittent connectivity and hybrid state information at the transmitter,” IEEE Transactions on Information Theory, vol. 64, no. 9, pp. 6362–6383, 2018.
  * [29] A. Vahid, M. A. Maddah-Ali, and A. S. Avestimehr, “Capacity results for binary fading interference channels with delayed CSIT,” IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 6093–6130, 2014.
  * [30] A. Vahid and R. Calderbank, “Throughput region of spatially correlated interference packet networks,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1220–1235, 2018.