# RANDAO-based RNG: Last Revealer Attacks in Ethereum 2.0 Randomness and a
Potential Solution

Do Hai Son<EMAIL_ADDRESS>VNU Information Technology InstituteHanoi,
Vietnam ,  Tran Thi Thuy Quynh<EMAIL_ADDRESS>University of Engineering
and TechnologyHanoi, Vietnam and  Le Quang Minh<EMAIL_ADDRESS>VNU
Information Technology InstituteHanoi, Vietnam

###### Abstract.

Ethereum 2.0 is a major upgrade to improve its scalability, throughput, and
security. In this version, RANDAO is the scheme to randomly select the users
who propose, confirm blocks, and get rewards. However, a vulnerability,
referred to as the ‘Last Revealer Attack’ (LRA), compromises the randomness of
this scheme by introducing bias to the Random Number Generator (RNG) process.
This vulnerability is first clarified again in this study. After that, we
propose a Shamir’s Secret Sharing (SSS)-based RANDAO scheme to mitigate the
LRA. Through our analysis, the proposed method can prevent the LRA under
favorable network conditions.

Last revealer attack, Ethereum, Shamir’s Secret Sharing, Verifiable Delay
Function

††copyright: none††ccs: Security and privacy††ccs: Security and privacy
Privacy-preserving protocols

##  1\. Introduction

Launching in 2016, Ethereum rapidly rose to rank 2nd in terms of crypto market
capitalization (marketcap, 4) due to its superior features, e.g., smart
contract, lower block confirmation time, and so forth. Hence, this network is
not only a digital asset but also a decentralized platform for other impactful
applications (Son2021, 14, 10). However, an intensive number of applications
brings the need to scale the Ethereum network and reduce the energy used for
mining (IEEESpectrum2019, 8) through the old consensus mechanism, i.e., Proof-
of-Work (PoW). Thus, in 2018, the Ethereum Foundation introduced the Ethereum
2.0 road map (Ethereumb, 9) to upgrade from PoW to Proof-of-Stake (PoS) using
Casper consensus (Buterin2020, 3). In 2020, the first phase on the road map,
named ‘Beacon chain’, was officially merged into the Ethereum mainnet. After
three years, the first phase is done with the highlight, which is a fully PoS-
based Ethereum network.

The move from PoW to PoS means the mining process is replaced by stakers, who
staked their money to become a validator. Any validator has the chance to
propose a new block, a.k.a proposer, and get a bounty of ETH (Ethereum native
token). In this work, we focus on the weakness of the random process to select
the proposer in Ethereum. According to Eth2.0 specs, this proposer is randomly
chosen by the RANDAO scheme (Ethereumb, 9) (Random decentralised autonomous
organisation). Generally, RANDAO is based on CRS (Commit reveal scheme)
(lastreveal, 2). In CRS, each member commits their value to a group, and the
final number is a combination of these values. However, in (Paul2018, 6), the
author indicated a vulnerability of the RANDAO scheme named LRA. This weakness
allows attackers to bias the RNG output. In (lastreveal, 2), Vitalik (Ethereum
Founder) pointed out that if an attacker had 36% of the total staked money, he
would gain control of the Ethereum network. This means the attacker
manipulates the proposers always to be his validators. That leads to the
consequence, i.e., he has the ability to validate any invalid blocks. The LRA
is similar to the 51% attack in Ethereum 1.0, but a massive amount of money
replaces the overwhelming computational power.

To deal with this vulnerability, the author in (Boneh2018, 1) proposed the VDF
(Verifiable Delay Function) algorithm. This method prevents any validator from
finding the final random number before the reveal phase. Following that, other
studies (Pietrzak2019, 11, 15, 7) proposed their versions of VDF, i.e., simple
VDF, efficient VDF, and continuous VDF, respectively. The Ethereum Foundation
confirmed the VDF version, named minimal VDF (mVDF, 5), which will be used in
the Ethereum mainnet after phase 2 on the road map. However, the drawback of
VDF is that this algorithm requires a specific hardware named ‘Rig’. Although
trustful organizations centrally control this device, it has lost the
decentralized properties of blockchain technology. In the worst case, none of
‘Rig’ is available, the VDF is turned down, and then Ethereum will switch back
to using the RANDAO scheme with the LRA weakness. In this work, we propose to
use the SSS (Shamir1979, 13) algorithm for the RANDAO process on Ethereum or
other Ethereum variants. SSS is an old but effective algorithm for securely
sharing a secret. Thus, SSS-based RANDAO can provide a controllable security
level to select proposers randomly. In Table 1, we explain several Ethereum
terms used in the following sections.

Table 1. Ethereum terms used in the paper

Term |  Description
---|---
Validator | Instead of ‘miner’ in PoW
Proposer | The chosen validator to propose blocks
Committee | A set of validators to validate the proposed blocks
Effective Balance | The current balance of a validator
Slot | Fixed at 12 seconds and equal to a block
Epoch | Consists of 32 slots

Our main contribution in this paper is to propose an SSS-based RANDAO scheme
for Ethereum 2.0. In this study, our proposal is a preliminary idea with some
security analysis to deal with the LRA attack on Ethereum.

The remainder of the paper is organized as follows. In Section 2, the brief
about LRA attack in RANDAO-based RNG is presented. In Section 3, we propose to
use Shamir’s Secret Sharing algorithm for randomly chosen proposers on
Ethereum. Finally, Section 4 concludes the paper.

##  2\. Last revealer attacks in RANDAO-based RNG

First, we briefly present the RANDAO-based RNG algorithm of Ethereum with an
illustration in Fig. 1. On Ethereum, the set of proposers and committees in
($j+2$)-th epoch is selected from the RANDAO-based results at ($j$)-th epoch.
At the first slot in $j$-th epoch, the proposer signs its BLS private_key on
the array of current epoch number ($j$) and fixed DOMAIN_RANDAO
(‘0x02000000’). The output of this process is a digital signature ($r_{1}$) in
size of $256$ bits that any validator can verify by the public_key of the
first proposer. This sequence of bits is included in the first slot in $j$-th
Epoch. Similarly, the second proposer computes its $256$-bits ($r_{2}$).
However, it does not immediately add this sequence to the block but computes

(1) $r_{2}=r_{1}\oplus r_{2},$

where $\oplus$ is the ‘XOR’ operator. The second proposer puts the computed
$r_{2}$ into its block. In the last slot, the sequence is as follows:

(2) $r_{32}=\oplus_{i}r_{i},\quad 1\leq i\leq 31.$

In the absence of a proposer case, the sequence is preserved as xor with a
series of zeros. The final sequence $r_{32}$ together with
DOMAIN_BEACON_PROPOSER (‘0x00000000’) and current epoch number ($j$) makes an
array called ‘seed32’. This array is passed through a hash function and
returns an array of 32 elements. The final array is one of the two inputs to
randomly select the set of proposers for ($j+2$)-th epoch. The latter input is
a set of all activated validators in the network at the first slot of $j$-th
epoch. The inputs are put into a deterministic function to select the set of
validators. Note that there is no randomness in this final validator selection
function. Hence, the randomness only comes from the ’seed32’ array, which is
contributed by a set of proposers.

Figure 1. Last revealer attacks on Ethereum.

In the LRA, suppose the attacker is the proposer holder in the 32-th slot. At
this stage, he already has information on the set of activated proposers from
the first slot and the mixed sequence ($r_{31}$) from the 31 slots previously.
Thus, he has two options, i.e., commit his digital signature as usual or
pretend to be absent to keep the $r_{31}$. This is a bias in the RNG process.
Note that only the last proposer can have this bias because the before
validators are infeasible to predict the after’s digital signature. That leads
to the name ‘Last revealer attack’. Furthermore, if the attacker has more than
one proposer in slots at the tail of an epoch, e.g., $h$ proposers, he will
have a total of $2^{h}$ options to decide whether to propose or not propose a
block. Consequently, these $2^{h}$ choices may introduce biases in the
selection of proposers and committees for the ($j+2$)-th epoch.

##  3\. Shamir’s Secret Sharing-based RANDAO

In this section, we present our proposal for SSS-based RNG to prevent the LRA
attack. After that, the security analysis and limitations of the proposed
scheme are provided.

###  3.1. Proposal

Our proposal is to apply the SSS algorithm to replace the CRS in RANDAO, as
mentioned in the previous section. SSS (Shamir1979, 13) threshold scheme based
on polynomial interpolation over finite fields. There are three definitions of
SSS ($n,m$), as follows:

  * •

Secret ($\mathbf{s}_{k}$): is the secret information (e.g., number, text,
etc.) that needs to be shared securely.

  * •

Share: is a part of the secret. For example, from an $\mathbf{s}_{k}$, we have
$m$ shares, i.e., $\mathbf{s}_{k}1$, $\mathbf{s}_{k}2$, …, $\mathbf{s}_{k}n$,
…, $\mathbf{s}_{k}m$.

  * •

Threshold ($n$): is the minimum number of shares required to recover the
original secret ($\mathbf{s}_{k}$).

Figure 2. SSS-based RANDAO.

As shown in Fig. 2, at the first slot, the proposer still computes its digital
signature ($r_{1}$), then divides $r_{1}$ into 31 shares ($m=31$)
corresponding to the rest of proposers in this epoch, i.e.,
$\mathbf{s}_{1}1,\mathbf{s}_{1}2,~{}\ldots,\mathbf{s}_{1}31$, respectively.
These shares are encrypted using asymmetric key schemes, e.g., RSA (RSA, 12),
so only the validator identified by its public key can reveal the
corresponding share. The first proposer then packs these shares into its block
and broadcasts the block to the network. The rest of the proposers also do the
same in their slots. At the last proposer, what it has is 31 shares (maximum),
i.e., $\mathbf{s}_{1}31,\mathbf{s}_{2}31,~{}\ldots,\mathbf{s}_{31}31$. Using
these shares, the last validator cannot recover any digital signature
($r_{i}$) from the rest of the proposers. This implies that it is not feasible
for this validator to manipulate the RNG process of RANDAO. After 32 slots (an
epoch), there is the reveal phase, when validators broadcast their decrypted
shares. Each secret from $i$-th proposer ($\mathbf{s}_{i}$) requires at least
$n$ shares ($n$ proposers broadcast their $\mathbf{s}_{k}i,\;1\leq i\leq n$,
decrypted shares) to recover. The unrecoverable $r_{i}$, due to not having
enough shares, can be treated as absent proposers, as RANDAO did. RANDAO
scheme selects proposers and committees for the $(j+2)$-th epoch from
recovered digital signatures and the set of activated validators. The reveal
and mixing phase in SSS-based RANDAO occurs after an epoch has been completed
and may lead to a delay in the timeline of Ethereum. Inspired by minimal VDF
(mVDF, 5), the reveal and mixing phase can be conducted in parallel as a
pipeline process.

###  3.2. Security analysis

Assume that $t,h$ is the number of proposers who joined SSS-based RANDAO and
the number of dishonest proposers in an epoch, respectively. In the first
case, as follows:

(3) $t\geq n\quad\textbf{and}\quad h<n,$

The proposed method can recover all secrets, and the attacker cannot predict
the digital signatures of other honest proposers. Thus, the LRA is prevented.
In the second case, as follows:

(4) $t<n,$

This is a bad case when we do not have enough shares to recover any secret.
This leads to no ‘seed32’ array, the original RANDAO mechanism will break, and
a backup solution is needed for this case. In the third case, when attackers
have a few proposers in an epoch, as follows:

(5) $t\geq n\quad\textbf{and}\quad h\geq n,$

Attackers have enough shares to recover secrets and compute the ‘seed32’ array
before starting the reveal phase. This leads to an attack similar to LRA, but
the attackers’ proposers do not need to be at the tail of the epoch.

The controllable property of the proposed scheme is that we can adapt the
threshold $n$ to guarantee the randomness of RANDAO-based RNG. However, it is
a trade-off because a higher $n$ means more proposers must be present in the
reveal phase.

##  4\. Conclusion

In this work, we proposed to use an SSS-based RANDAO scheme instead of CRS to
mitigate the LRA. We first represented the RANDAO-based RNG of Ethereum and
pointed out its weakness. The SSS algorithm is applied to RANDAO and shows its
advantages and limitations. Our study is still in its preliminary stages and
requires further analysis to estimate the amount of stake attackers need to
control the mechanism we have proposed.

## References

  * (1) Dan Boneh, Joseph Bonneau, Benedikt Bünz and Ben Fisch  “Verifiable delay functions”  In _Annual international cryptology conference_ , 2018, pp. 757–788  Springer
  * (2) Vitalik Buterin  “RANDAO beacon exploitability analysis, round 2”  URL: https://ethresear.ch/t/randao-beacon-exploitability-analysis-round-2/1980
  * (3) Vitalik Buterin et al.  “Combining GHOST and Casper”, 2020, pp. 1–38  arXiv: http://arxiv.org/abs/2003.03052
  * (4) CoinMarketCap  “Cryptocurrency Prices, Charts And Market Capitalizations”  URL: https://coinmarketcap.com
  * (5) Justin Drake  “Minimal VDF randomness beacon”  URL: https://ethresear.ch/t/minimal-vdf-randomness-beacon/3566
  * (6) Paul Dworzanski  “A Note On Committee Random Number Generation, Commit-Reveal, And Last-Revealer Attacks”  URL: https://ethresear.ch/t/limiting-last-revealer-attacks-in-beacon-chain-randomness/3705
  * (7) Naomi Ephraim, Cody Freitag, Ilan Komargodski and Rafael Pass  “Continuous verifiable delay functions”  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2020, pp. 125–154  Springer
  * (8) Peter Fairley  “Ethereum Plans to Cut Its Absurd Energy Consumption by 99 Percent”, 2019  URL: https://spectrum.ieee.org/computing/networks/ethereum-plans-to-cut-its-absurd-energy-consumption-by-99-percent
  * (9) Ethereum Foundation  “Ethereum 2.0 Specifications”  URL: https://github.com/ethereum/eth2.0-specs
  * (10) Shi-Yi Lin et al.  “A survey of application research based on blockchain smart contract”  In _Wireless Networks_ 28.2 Springer, 2022, pp. 635–690
  * (11) Krzysztof Pietrzak  “Simple verifiable delay functions”  In _10th innovations in theoretical computer science conference (ITCS 2019)_ , 2019
  * (12) R.. Rivest, A. Shamir and L. Adleman  “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”  In _Commun. ACM_ 21.2 New York, NY, USA: Association for Computing Machinery, 1978, pp. 120–126
  * (13) Adi Shamir  “How to Share a Secret”  In _Commun. ACM_ 22.11 New York, NY, USA: Association for Computing Machinery, 1979, pp. 612–613
  * (14) Do Hai Son et al.  “An Effective Framework of Private Ethereum Blockchain Networks for Smart Grid”  In _2021 International Conference on Advanced Technologies for Communications (ATC)_ , 2021, pp. 312–317
  * (15) Benjamin Wesolowski  “Efficient verifiable delay functions”  In _Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2019, pp. 379–407


# A Copy-Augmented Sequence-to-Sequence Architecture Gives
Good Performance on Task-Oriented Dialogue

Mihail Eric  Christopher D. Manning
Computer Science Department
Stanford University
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Task-oriented dialogue focuses on conversational agents that participate in
dialogues with user goals on domain-specific topics. In contrast to chatbots,
which simply seek to sustain open-ended meaningful discourse, existing task-
oriented agents usually explicitly model user intent and belief states. This
paper examines bypassing such an explicit representation by depending on a
latent neural embedding of state and learning selective attention to dialogue
history together with copying to incorporate relevant prior context. We
complement recent work by showing the effectiveness of simple sequence-to-
sequence neural architectures with a copy mechanism. Our model outperforms
more complex memory-augmented models by 7% in per-response generation and is
on par with the current state-of-the-art on DSTC2, a real-world task-oriented
dialogue dataset.

##  1 Introduction

Effective task-oriented dialogue systems are becoming important as society
progresses toward using voice for interacting with devices and performing
everyday tasks such as scheduling. To that end, research efforts have focused
on using machine learning methods to train agents using dialogue corpora. One
line of work has tackled the problem using partially observable Markov
decision processes and reinforcement learning with carefully designed action
spaces [2013]. However, the large, hand-designed action and state spaces make
this class of models brittle and unscalable, and in practice most deployed
dialogue systems remain hand-written, rule-based systems.

Recently, neural network models have achieved success on a variety of natural
language processing tasks [2015, 2014, 2015], due to their ability to
implicitly learn powerful distributed representations from data in an end-to-
end trainable fashion. This paper extends recent work examining the utility of
distributed state representations for task-oriented dialogue agents, without
providing rules or manually tuning features.

One prominent line of recent neural dialogue work has continued to build
systems with modularly-connected representation, belief state, and generation
components [2016b]. These models must learn to explicitly represent user
intent through intermediate supervision, and hence suffer from not being truly
end-to-end trainable. Other work stores dialogue context in a memory module
and repeatedly queries and reasons about this context to select an adequate
system response [2016]. While reasoning over memory is appealing, these models
simply choose among a set of utterances rather than generating text and also
must have temporal dialogue features explicitly encoded.

However, the present literature lacks results for now standard sequence-to-
sequence architectures, and we aim to fill this gap by building increasingly
complex models of text generation, starting with a vanilla sequence-to-
sequence recurrent architecture. The result is a simple, intuitive, and highly
competitive model, which outperforms the more complex model of ?) by 6.9%. Our
contributions are as follows: 1) We perform a systematic, empirical analysis
of increasingly complex sequence-to-sequence models for task-oriented
dialogue, and 2) we develop a recurrent neural dialogue architecture augmented
with an attention-based copy mechanism that is able to significantly
outperform more complex models on a variety of metrics on realistic data.

##  2 Architecture

We use neural encoder-decoder architectures to frame dialogue as a sequence-
to-sequence learning problem. Given a dialogue between a user (_u_) and a
system (_s_), we represent the dialogue utterances as
$\\{(u_{1},s_{1}),(u_{2},s_{2}),\ldots,(u_{k},s_{k})\\}$ where $k$ denotes the
number of turns in the dialogue. At the $i{{}^{\mbox{th}}}$ turn of the
dialogue, we encode the aggregated dialogue context composed of the tokens of
$(u_{1},s_{1},\ldots,s_{i-1},u_{i})$. Letting $x_{1},\ldots,x_{m}$ denote
these tokens, we first embed these tokens using a trained embedding function
$\phi^{emb}$ that maps each token to a fixed-dimensional vector. These
mappings are fed into the encoder to produce context-sensitive hidden
representations $h_{1},\ldots,h_{m}$.

The vanilla Seq2Seq decoder predicts the tokens of the $i{{}^{\mbox{th}}}$
system response $s_{i}$ by first computing decoder hidden states via the
recurrent unit. We denote $\tilde{h}_{1},\ldots,\tilde{h}_{n}$ as the hidden
states of the decoder and $y_{1},\ldots,y_{n}$ as the output tokens. We extend
this decoder with an attention-based model [2015, 2015a], where, at every time
step $t$ of the decoding, an attention score $a_{i}^{t}$ is computed for each
hidden state $h_{i}$ of the encoder, using the attention mechanism of [2015].
Formally this attention can be described by the following equations:

$\displaystyle u_{i}^{t}$
$\displaystyle=v^{T}\tanh(W_{1}h_{i}+W_{2}\tilde{h}_{t})$ (1) $\displaystyle
a_{i}^{t}$ $\displaystyle=\textrm{Softmax}(u_{i}^{t})$ (2)
$\displaystyle\tilde{h}_{t}^{\prime}$
$\displaystyle=\displaystyle\sum_{i=1}^{m}a_{i}^{t}h_{i}$ (3) $\displaystyle
o_{t}$ $\displaystyle=U[\tilde{h}_{t},\tilde{h}_{t}^{\prime}]$ (4)
$\displaystyle y_{t}$ $\displaystyle=\textrm{Softmax}(o_{t})$ (5)

where $W_{1}$, $W_{2}$, $U$, and $v$ are trainable parameters of the model and
$o_{t}$ represents the logits over the tokens of the output vocabulary $V$.
During training, the next token $y_{t}$ is predicted so as to maximize the
log-likelihood of the correct output sequence given the input sequence.

An effective task-oriented dialogue system must have powerful language
modelling capabilities and be able to pick up on relevant entities of an
underlying knowledge base. One source of relevant entities is that they will
commonly have been mentioned in the prior discourse context. Recent literature
has shown that incorporating a copying mechanism into neural architectures
improves performance on various sequence-to-sequence tasks including code
generation, machine translation, and text summarization [2016, 2016, 2016]. We
therefore augment the attention encoder-decoder model with an attention-based
copy mechanism in the style of [2016]. In this scheme, during decoding we
compute our new logits vector as
$o_{t}=U[\tilde{h}_{t},\tilde{h}_{t}^{\prime},a^{t}_{[1:m]}]$ where
$a^{t}_{[1:m]}$ is the concatenated attention scores of the encoder hidden
states, and we are now predicting over a vocabulary of size $|V|+m$. The
model, thus, either predicts a token $y_{t}$ from $V$ or copies a token
$x_{i}$ from the encoder input context, via the attention score $a_{i}^{t}$.
Rather than copy over any token mentioned in the encoder dialogue context, our
model is trained to only copy over entities of the knowledge base mentioned in
the dialogue context, as this provides a conceptually intuitive goal for the
model’s predictive learning: as training progresses it will learn to either
predict a token from the standard vocabulary of the language model thereby
ensuring well-formed natural language utterances, or to copy over the relevant
entities from the input context, thereby learning to extract important
dialogue context.

In our best performing model, we augment the inputs to the encoder by adding
entity type features. Classes present in the knowledge base of the dataset,
namely the 8 distinct entity types referred to in Table 1, are encoded as one-
hot vectors. Whenever a token of a certain entity type is seen during
encoding, we append the appropriate one-hot vector to the token’s word
embedding before it is fed into the recurrent cell. These type features
improve generalization to novel entities by allowing the model to hone in on
positions with particularly relevant bits of dialogue context during its soft
attention and copying. Other cited work using the DSTC2 dataset [2016, 2016,
2016] implement similar mechanisms whereby they expand the feature
representations of candidate system responses based on whether there is
lexical entity class matching with provided dialogue context. In these works,
such features are referred to as _match_ features.

All of our architectures use an LSTM cell as the recurrent unit [1997] with a
bias of 1 added to the forget gate in the style of [2014].

##  3 Experiments

###  3.1 Data

For our experiments, we used dialogues extracted from the Dialogue State
Tracking Challenge 2 (DSTC2) [2014], a restaurant reservation system dataset.
While the goal of the original challenge was building a system for inferring
dialogue state, for our study, we use the version of the data from ?), which
ignores the dialogue state annotations, using only the raw text of the
dialogues. The raw text includes user and system utterances as well as the API
calls the system would make to the underlying KB in response to the user’s
queries. Our model then aims to predict both these system utterances and API
calls, each of which is regarded as a turn of the dialogue. We use the
train/validation/test splits from this modified version of the dataset. The
dataset is appealing for a number of reasons: 1) It is derived from a real-
world system so it presents the kind of linguistic diversity and
conversational abilities we would hope for in an effective dialogue agent. 2)
It is grounded via an underlying knowledge base of restaurant entities and
their attributes. 3) Previous results have been reported on it so we can
directly compare our model performance. We include statistics of the dataset
in Table 1.

###  3.2 Training

We trained using a cross-entropy loss and the Adam optimizer [2015], applying
dropout [2012] as a regularizer to the input and output of the LSTM. We
identified hyperparameters by random search, evaluating on a held-out
validation subset of the data. Dropout keep rates ranged from 0.75 to 0.95. We
used word embeddings with size 300, and hidden layer and cell sizes were set
to 353, identified through our search. We applied gradient clipping with a
clip-value of 10 to avoid gradient explosions during training. The attention,
output parameters, word embeddings, and LSTM weights were randomly initialized
from a uniform unit-scaled distribution in the style of [2015].

| Avg. # of Utterances Per Dialogue | 14
---|---
Vocabulary Size | 1,229
Training Dialogues | 1,618
Validation Dialogues | 500
Test Dialogues | 1,117
# of Distinct Entities | 452
# of Entity (or Slot) Types | 8
Table 1: Statistics of DSTC2

###  3.3 Metrics

Evaluation of dialogue systems is known to be difficult [2016]. We employ
several metrics for assessing specific aspects of our model, drawn from
previous work:

  * •

Per-Response Accuracy: Bordes and Weston [2016] report a per-turn response
accuracy, which tests their model’s ability to select the system response at a
certain timestep. Their system does a multiclass classification over a
predefined candidate set of responses, which was created by aggregating all
system responses seen in the training, validation, and test sets. Our model
actually generates each individual token of the response, and we consider a
prediction to be correct only if every token of the model output matches the
corresponding token in the gold response. Evaluating using this metric on our
model is therefore significantly more stringent a test than for the model of
Bordes and Weston [2016].

  * •

Per-Dialogue Accuracy: Bordes and Weston [2016] also report a per-dialogue
accuracy, which assesses their model’s ability to produce every system
response of the dialogue correctly. We calculate a similar value of dialogue
accuracy, though again our model generates every token of every response.

  * •

BLEU: We use the BLEU metric, commonly employed in evaluating machine
translation systems [2002], which has also been used in past literature for
evaluating dialogue systems [2011, 2016]. We calculate average BLEU score over
all responses generated by the system, and primarily report these scores to
gauge our model’s ability to accurately generate the language patterns seen in
DSTC2.

  * •

Entity F1: Each system response in the test data defines a gold set of
entities. To compute an entity F1, we micro-average over the entire set of
system dialogue responses. This metric evaluates the model’s ability to
generate relevant entities from the underlying knowledge base and to capture
the semantics of the user-initiated dialogue flow.

Our experiments show that sometimes our model generates a response to a given
input that is perfectly reasonable, but is penalized because our evaluation
metrics involve direct comparison to the gold system output. For example,
given a user request for an _australian restaurant_ , the gold system output
is _you are looking for an australian restaurant right?_ whereas our system
outputs _what part of town do you have in mind?_ , which is a more directed
follow-up intended to narrow down the search space of candidate restaurants
the system should propose. This issue, which recurs with evaluation of
dialogue or other generative systems, could be alleviated through more
forgiving evaluation procedures based on beam search decoding.

###  3.4 Results

In Table 2, we present the results of our models compared to the reported
performance of the best performing model of [2016], which is a variant of an
end-to-end memory network [2015]. Their model is referred to as _MemNN_. We
also include the model of [2016], referred to as _GMemNN_ , and the model of
[2016], referred to as _QRN_ , which currently is the state-of-the-art. In the
table, Seq2Seq refers to our vanilla encoder-decoder architecture with (1),
(2), and (3) LSTM layers respectively. +Attn refers to a 1-layer Seq2Seq with
attention-based decoding. +Copy refers to +Attn with our copy-mechanism added.
+EntType refers to +Copy with entity class features added to encoder inputs.

We see that a 1-layer vanilla encoder-decoder is already able to significantly
outperform _MemNN_ in both per-response and per-dialogue accuracies, despite
our more stringent setting. Adding layers to Seq2Seq leads to a drop in
performance, suggesting an overly powerful model for the small dataset size.
Adding an attention-based decoding to the vanilla model increases BLEU
although per-response and per-dialogue accuracies suffer a bit. Adding our
attention-based entity copy mechanism achieves substantial increases in per-
response accuracies and entity F1. Adding entity class features to +Copy
achieves our best-performing model, in terms of per-response accuracy and
entity F1. This model achieves a 6.9% increase in per-response accuracy on
DSTC2 over _MemNN_ , including +1.5% per-dialogue accuracy, and is on par with
the performance of _GMemNN_ , including beating its per-dialogue accuracy. It
also achieves the highest entity F1.

Data | Model | Per- | Per | BLEU | Ent.
---|---|---|---|---|---
|  | Resp. | Dial. |  | F1
Test | _MemNN_ | 41.1 | 0.0 | – | –
set | _GMemNN_ | 48.7 | 1.4 | – | –
| _QRN_ | 50.7 | – | – | –
| Seq2Seq (1) | 46.4 | 1.5 | 55.0 | 69.7
| Seq2Seq (2) | 43.5 | 1.3 | 54.2 | 67.3
| Seq2Seq (3) | 44.2 | 1.7 | 55.4 | 65.9
|  \+ Attn. | 46.0 | 1.4 | 56.6 | 67.1
|  \+ Copy | 47.3 | 1.3 | 55.4 | 71.6
|  \+ EntType | 48.0 | 1.5 | 56.0 | 72.9
Dev | Seq2Seq (1) | 57.0 | 3.6 | 72.1 | 68.7
set | Seq2Seq (2) | 54.1 | 3.0 | 71.3 | 66.3
| Seq2Seq (3) | 54.0 | 3.2 | 71.5 | 64.3
|  \+ Attn. | 55.2 | 3.4 | 71.9 | 66.1
|  \+ Copy | 58.9 | 3.6 | 73.1 | 72.5
|  \+ EntType | 59.2 | 3.4 | 72.7 | 72.3
Table 2: Evaluation on DSTC2 test (top) and dev (bottom) data. Bold values
indicate our best performance. A dash indicates unavailable values.

##  4 Discussion and Conclusion

We have iteratively built out a class of neural models for task-oriented
dialogue that is able to outperform other more intricately designed neural
architectures on a number of metrics. The model incorporates in a simple way
abilities that we believe are essential to building good task-oriented
dialogue agents, namely maintaining dialogue state and being able to extract
and use relevant entities in its responses, without requiring intermediate
supervision of dialogue state or belief tracker modules. Other dialogue models
tested on DSTC2 that are more performant in per-response accuracy are equipped
with sufficiently more complex mechanisms than our model. Taking inspiration
from [2015] and [2015], _GMemNN_ uses an explicit memory module as well as an
adaptive gating mechanism to learn to attend to relevant memories. The _QRN_
model employs a variant of a recurrent unit that is intended to handle local
and global interactions in sequential data. We contrast with these works by
bootstrapping off of more empirically accepted Seq2Seq architectures through
intuitive extensions, while still producing highly competitive models.

We attribute the large gains in per-response accuracy and entity F1
demonstrated by our +EntType to its ability to pick out the relevant KB
entities from the dialogue context fed into the encoder. In Figure 1, we see
the attention-based copy weights of the model, indicating that the model is
able to learn the relevant entities it should focus on in the input context.
The powerful language modelling abilities of the Seq2Seq backbone allow smooth
integration of these extracted entities into both system-generated API calls
and natural language responses as shown in the figure.

| cheap restaurant in east part of town
---
_api_call r_cuisine east cheap_
$<$silence$>$
_the_missing_sock is a nice place in the_
_east of town and the prices are cheap_
address
_sure, the_missing_sock is on the_missing_sock_address_
phone number
_the phone number of the_missing_sock is_
_the_missing_sock_phone_
thank you good bye
_you are welcome_
Table 3: Sample dialogue generated. System responses are in italics. The
dataset uses fake addresses and phone numbers. Figure 1: Attention-copy
weights for a generated natural language response (top) and API call (bottom).
The decoder output is displayed vertically and the encoder input is
abbreviated for display.

The appeal of our model comes from the simplicity and effectiveness of framing
system response generation as a sequence-to-sequence mapping with a soft copy
mechanism over relevant context. Unlike the task-oriented dialogue agents of
Wen et. al [2016b], our architecture does not explicitly model belief states
or KB slot-value trackers, and we preserve full end-to-end-trainability.
Further, in contrast to other referenced work on DSTC2, our model offers more
linguistic versatility due to its generative nature while still remaining
highly competitive and outperforming other models. Of course, this is not to
deny the importance of dialogue agents which can more effectively use a
knowledge base to answer user requests, and this remains a good avenue for
further work. Nevertheless, we hope this simple and effective architecture can
be a strong baseline for future research efforts on task-oriented dialogue.

## Acknowledgments

The authors wish to thank the reviewers, Lakshmi Krishnan, Francois Charette,
and He He for their valuable feedback and insights. We gratefully acknowledge
the funding of the Ford Research and Innovation Center, under Grant No.
124344. The views expressed here are those of the authors and do not
necessarily represent or reflect the views of the Ford Research and Innovation
Center.

## References

  * [2015]  Dzimitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  2015\.  Neural machine translation by jointly learning to align and translate.  In International Conference on Learning Representations (ICLR2015).
  * [2016]  Antoine Bordes and Jason Weston.  2016\.  Learning end-to-end goal-oriented dialog.  arXiv preprint arXiv:1605.07683.
  * [2016]  Jiatao Gu, Zhengdong Lu, Hang Li, and Victor O.K. Li.  2016\.  Incorporating copying mechanism in sequence-to-sequence learning.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1631–1640, Berlin, Germany, August. Association for Computational Linguistics.
  * [2016]  Caglar Gulcehre, Sungjin Ahn, Ramesh Nallapati, Bowen Zhou, and Yoshua Bengio.  2016\.  Pointing the unknown words.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 140–149, Berlin, Germany, August. Association for Computational Linguistics.
  * [2014]  Matthew Henderson, Blaise Thomson, and Jason Williams.  2014\.  The second dialog state tracking challenge.  15th Annual Meeting of the Special Interest Group on Discourse and Dialogue, page 263.
  * [2012]  Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R. Salakhutdinov.  2012\.  Improving neural networks by preventing co-adaptation of feature detectors.  arXiv preprint arXiv:1207.0580.
  * [1997]  Sepp Hochreiter and Jurgen Schmidhuber.  1997\.  Long short-term memory.  Neural Computation, pages 1735––1780.
  * [2016]  Robin Jia and Percy Liang.  2016\.  Data recombination for neural semantic parsing.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12–22, Berlin, Germany, August. Association for Computational Linguistics.
  * [2015]  Diederik Kingma and Jimmy Ba.  2015\.  Adam: a method for stochastic optimization.  In International Conference on Learning Representations (ICLR2015).
  * [2016]  Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan.  2016\.  A diversity-promoting objective function for neural conversation models.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 110–119, San Diego, California, June. Association for Computational Linguistics.
  * [2016]  Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Fumin Wang, and Andrew Senior.  2016\.  Latent predictor networks for code generation.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 599–609, Berlin, Germany, August. Association for Computational Linguistics.
  * [2016]  Fei Liu and Julien Perez.  2016\.  Gated end-to-end memory networks.  arXiv preprint arXiv:1610.04211.
  * [2016]  Chia-Wei Liu, Ryan Lowe, Iulian Serban, Mike Noseworthy, Laurent Charlin, and Joelle Pineau.  2016\.  How not to evaluate your dialogue system: An empirical study of unsupervised evaluation metrics for dialogue response generation.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2122–2132, Austin, Texas, November. Association for Computational Linguistics.
  * [2015a]  Minh-Thang Luong, Hieu Pham, and Christopher D. Manning.  2015a.  Effective approaches to attention-based neural machine translation.  Empirical Methods in Natural Language Processing, pages 1412––1421.
  * [2002]  Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  2002\.  Bleu: a method for automatic evaluation of machine translation.  In Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA, July. Association for Computational Linguistics.
  * [2014]  Vu Pham, Theodore Bluche, Christopher Kermorvant, and Jerome Louradour.  2014\.  Dropout improves recurrent neural networks for handwriting recognition.  arXiv preprint arXiv:1312.4569v2.
  * [2011]  Alan Ritter, Colin Cherry, and William B. Dolan.  2011\.  Data-driven response generation in social media.  Empirical Methods in Natural Language Processing, pages 583–593.
  * [2016]  Minjoon Seo, Sewon Min, Ali Farhadi, and Hannaneh Hajishirzi.  2016\.  Query-reduction networks for question answering.  arXiv preprint arXiv:1606.04582.
  * [2015]  Rupesh Srivastava, Klaus Greff, and Jurgen Schmidhuber.  2015\.  Highway networks.  In International Conference on Learning Representations (ICLR2015).
  * [2015]  Sainbayar Sukhbaatar, arthur szlam, Jason Weston, and Rob Fergus.  2015\.  End-to-end memory networks.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2440–2448. Curran Associates, Inc.
  * [2015]  David Sussillo and L.F. Abbott.  2015\.  Random walk initialization for training very deep feed forward networks.  arXiv preprint arXiv:1412.6558.
  * [2014]  Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  2014\.  Sequence to sequence learning with neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3104–3112. Curran Associates, Inc.
  * [2015]  Oriol Vinyals, Ł ukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton.  2015\.  Grammar as a foreign language.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2773–2781. Curran Associates, Inc.
  * [2016b]  Tsung-Hsien Wen, David Vandyke, Milica Gasic, Nikola Mrksic, Lina. M. Rojas-Barahona, Pei-Hao Su, Stefan Ultes, and Steve Young.  2016b.  A network-based end-to-end trainable task-oriented dialogue system.  arXiv preprint arXiv:1604.04562.
  * [2013]  Steve Young, Milica Gasic, Blaise Thomson, and Jason D. Williams.  2013\.  POMDP-based statistical spoken dialog systems: a review.  Proceedings of the IEEE, 28(1):114–133.


# Topological Content Delivery with
Feedback and Random Receiver Cache

Alireza Vahid  Alireza Vahid is with the Electrical Engineering Department of
the University of Colorado Denver, Denver, CO, USA. Email:
<EMAIL_ADDRESS>
###### Abstract

We study the problem of content delivery in two-user interference channels
with altering topology, random available cache at the receivers, and delayed
channel knowledge at the transmitter. We establish a new set of outer-bounds
on the achievable rates when each receiver has access to a random fraction of
the message intended for the other receiver, and when each transmitter is
aware of which part of its own message is known to the unintended receiver.
The outer-bounds reveal the significant potential rate boost associated with
even a small amount of side-information at each receiver. The key in deriving
the bounds is to quantify the baseline entropy that will always become
available to the unintended receiver given the altering topology and the
already available side-information. We will also present matching achievable
rates in certain scenarios and outline the challenges in more general
settings.

###### Index Terms:

Random cache, interference channel, packet erasure, side-information, causal
feedback, channel state information.

##  I Introduction

Smartly populating the available local memory, or cache, can greatly enhance
the data throughput and latency in wireless networks [1, 2, 3, 4, 5, 6].
Unfortunately, predetermining what needs to be placed at each user’s local
cache may not be feasible in practice due to privacy issues, lack of
centralized decision-making, and mobility of the wireless nodes. In this work,
we focus on the benefit of random receiver cache in wireless systems wherein
users overhear a random portion of the signal intended for other users through
the shared medium. In particular, we do not rely on a conventional two phase
strategy where the first phase is for content placement, and the second is for
content delivery. Instead, we investigate how to harness the random signal
that has become available to different users in order to enhance network
throughput.

To provide fundamental results on the capacity region in such scenarios, we
focus on interference channels with altering topology. More specifically, we
consider the canonical two-user interference channel where each wireless link
may be active or inactive (or down) according to some Markov process, and
these processes may be correlated across users. This model has grown popular
in recent years as it provides a suitable framework to study intermittent
communications in massive machine-type systems and high packet failure rate in
mmWave communications. We provide a brief summary of the efforts on this model
later in the introduction. The randomness in the available receiver-end cache
is generated by independent erasure processes, and the transmitters are aware
of which portion of their own messages is available to the unintended
receiver. We further assume the transmitters become aware of the network
topology with unit delay, a suitable model for mmWave and machine-type
communications. As the topology is captured by whether each link is active or
not, this latter assumption can be thought of as the delayed channel state
information at the transmitter (delayed CSIT) model.

Contributions: We present a new set of outer-bounds on the capacity region of
the two-user interference channel with altering topology and channel state
feedback. The first step in the derivation of the outer-bounds is to quantify
the baseline entropy that will always become available to the unintended user
regardless of the communication strategy. In particular, the key is to
incorporate the apriori side-information at each receiver’s local cache, the
altering topology, and the delayed channel feedback into our analysis. Next,
the outer-bounds are derived by using a genie-aided argument to convert the
channel into a one-sided interference channel and then, the bounds are
obtained by applying the baseline entropy inequality discussed above. The
outer-bounds of course recover those known previously in the literature for
the no-cache and full-cache (when the entire message of each user is available
to the other one) scenarios. Interestingly, the outer-bounds suggest even a
small amount of side-information may drastically improve the capacity region
as we will discuss later in the paper.

We then investigate under what conditions these outer-bounds can be achieved.
We provide two sets of conditions. First, we show for “strong channels” and
“small cache” sizes (to be quantified in the main results), we can achieve the
sum-capacity with symmetric channel parameters. Second, we identify a subset
of these conditions for which the entire outer-bound region can be achieved
and thus, characterizing the capacity region in those cases. We will highlight
the challenges when these conditions are not met and discuss whether we
believe the inner or the outer-bounds need to be improved.

Summary of Results on Interference Channels with Altering Topology: The
interference channel with altering topology or the erasure interference
channel (EIC) was first introduced in [7], where it was referred to as the
“binary fading” model, to generalize the erasure channel to incorporate
interference from other transmitters. The capacity region of the two-user EIC
with output feedback was reported in [8] followed by a comprehensive set of
results covering the capacity region under delayed and instantaneous CSIT with
or without output feedback in [9]. The model and the results were shown to be
a good representative of mmWave packet communications [10, 11, 12] and
topological dynamics of wireless networks [13, 14]. The model was also proven
valuable in studying the impact of channel correlation [15, 16] and local
delayed knowledge [17, 18] on the capacity of distributed wireless networks.
Interestingly, the capacity region under the no CSIT assumption and arbitrary
erasure probabilities remains open, and the best known inner and outer bounds
were reported in [19] with alternative proof in [20, 21], echoing the famous
“W-curve” result of [22]. The model has also been used to study the stability
region of interference channels [23] where newer coding techniques compared to
the study of the capacity region were reported. Finally, this model was
adopted in [24, 25] to investigate the coexistence of critical and non-
critical IoT services.

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 outer-bounds are presented in
Section IV, and the achievability region is derived in Section V. Finally,
Section VI concludes the paper.

##  II Problem Formulation

To quantify the impact of available random receiver cache on the capacity
region of interference channels with altering topology, we consider the
canonical two-user erasure interference channel (EIC) of Figure 1. The erasure
channel model captures altering network topology [13] or packet failure [10].
In this network, two single-antenna transmitters, $\mathsf{Tx}_{1}$ and
$\mathsf{Tx}_{2}$, wish to transmit two independent messages, $W_{1}$ and
$W_{2}$, to their corresponding single-antenna receiving terminals,
$\mathsf{Rx}_{1}$ and $\mathsf{Rx}_{2}$, respectively, over $n$ channel uses.

Figure 1: The two-user interference channel with altering topology, random
local cache at the receivers, and delayed channel knowledge. Each wireless
link may be active or down, creating all possible topology configurations for
this network.

Channel model: The channel gain from transmitter ${\sf Tx}_{j}$ to receiver
${\sf Rx}_{i}$ at time $t$ is denoted by $G_{ij}[t]$, $i,j\in\\{1,2\\}$. The
channel gains are either $0$ or $1$ (_i.e._ $G_{ij}[t]\in\\{0,1\\}$), and they
are distributed as Bernoulli random variables. The channels are assumed to be
distributed independently across time but not necessarily across users. Here,
when a channel value is equal to $0$, the receiver does not obtain the
corresponding transmitter’s signal. We assume:

$\displaystyle\Pr\left(G_{ij}[t]=0\right)=\delta_{ij}\qquad i,j\in\\{1,2\\},$
$\displaystyle\Pr\left(G_{i1}[t]=0,G_{i2}[t]=0\right)=\delta_{{\sf
Rx}_{i}}\qquad i=1,2,$
$\displaystyle\Pr\left(G_{1j}[t]=0,G_{2j}[t]=0\right)=\delta_{{\sf
Tx}_{j}}\qquad j=1,2,$ (1)

for $0\leq\delta_{ij},\delta_{{\sf Rx}_{i}},\delta_{{\sf Tx}_{j}}\leq 1$. We
note that when the channel gains are distributed independently across users,
we have

$\displaystyle\delta_{{\sf
Rx}_{i}}=\delta_{i1}\delta_{i2},\qquad\text{and}\qquad\delta_{{\sf
Tx}_{j}}=\delta_{1j}\delta_{2j}.$ (2)

Input and output signals: At each time instant $t$, the transmit signal of
${\sf Tx}_{j}$ is denoted by $X_{j}[t]\in\\{0,1\\}$, and the received signal
at ${\sf Rx}_{i}$ is given by

$Y_{i}[t]=G_{ii}[t]X_{i}[t]\oplus G_{i\bar{i}}[t]X_{\bar{i}}[t],\quad
i=1,2,\quad\bar{i}\overset{\triangle}{=}3-i,$ (3)

where all algebraic operations are in $\mathbb{F}_{2}$. We note that one could
assign a continuous channel gain beyond the binary coefficient and also assume
additive noise at the receivers, however, this will not change the fundamental
of this problem as was the case in [13, 14]. Further, the results can be
easily extended to the case where signals are in $\mathbb{F}_{q}$ and a
correction factor of $\log_{2}q$ will be added to the inner and outer bounds.

######  Remark 1.

Each point-to-point link in this network is effectively an erasure channel,
but instead of representing the output by a symbol in $\\{0,e,1\\}$, we use a
channel gain in the binary field. When the link is equal to $1$ (_i.e._ the
link is on), the binary output equals to the input, and when the link is equal
to $0$ (_i.e._ the link is off), the output is deterministically zero. Below,
we explain that the receiver knows the channel value, and thus, can map the
observed zero due to the channel being off to an erasure. This way of modeling
enables us to easily describe interference at each receiver as in (3).

Channel state information: We define the channel state information (CSI) at
time $t$ to be the quadruple

$\displaystyle
G[t]\overset{\triangle}{=}\left(G_{11}[t],G_{12}[t],G_{21}[t],G_{22}[t]\right),$
(4)

and for natural number $k$, we set

$\displaystyle
G^{k}\overset{\triangle}{=}\left(G[1],G[2],\ldots,G[k]\right)^{\top},$ (5)

where $G[t]$ is defined in (4), and $\left(\cdot\right)^{\top}$ denotes the
transpose operation. Finally, we set

$\displaystyle G_{ii}^{t}X_{i}^{t}\oplus
G_{i\bar{i}}^{t}X_{\bar{i}}^{t}\overset{\triangle}{=}\left[G_{ii}[1]X_{i}[1]\oplus
G_{i\bar{i}}[1]X_{\bar{i}}[1],\ldots,G_{ii}[t]X_{i}[t]\oplus
G_{i\bar{i}}[t]X_{\bar{i}}[t]\right]^{\top}.$ (6)

Messages: Each message, $W_{i}$, contains $m_{i}$ data packets, and we denote
the packets for $\mathsf{Rx}_{1}$ with
$\vec{a}=\left(a_{1},a_{2},\ldots,a_{m_{1}}\right)$, and the packets for
$\mathsf{Rx}_{2}$ with $\vec{b}=\left(b_{1},b_{2},\ldots,b_{m_{2}}\right)$.
Here, we note 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. As mentioned earlier, if we assume
the packets are in $\mathbb{F}_{q}$ instead, all that would be needed is a
correction factor of $\log_{2}q$ in the inner and outer bounds.

Available CSI at the Transmitters: In this work, we consider the delayed CSIT
model in which at time $t$, each transmitter has the knowledge of the channel
state information up to the previous time instant (_i.e._ $G^{t-1}$) as
depicted in Figure 1, and the distribution from which the channel gains are
drawn, $t=1,2,\ldots,n$.

Available CSI at the Receivers: At time instant $t$, ${\sf Rx}_{i}$ has the
its local channel state information up to time $t$ (_i.e._ $G_{ii}^{t}$ and
$G_{i\bar{i}}^{t}$), see Figure 1, and the distribution from which the channel
gains are drawn. Each receiver then broadcasts its local CSI which becomes
available to all other nodes with unit delay. To make notations simpler, and
since receivers only decode the messages at the end of the communication
block, we assume both receivers have instantaneous knowledge of the entire
CSI. We note that each channel gain in the intermittent (erasure) model
captures the success or the failure in delivering a large number of bits in
the forward channel, and thus, the feedback overhead is negligible. This also
explains why the feedback channel is used to share CSI rather than information
about the received signals as in [26, 27] (_i.e._ the channel output feedback
assumption).

Random receiver cache: We assume a random fraction $(1-\epsilon_{i})$ of the
bits intended for receiver $\mathsf{Rx}_{\bar{i}}$ are available at
$\mathsf{Rx}_{{i}}$, $\bar{i}=3-i$, and we denote this side information with
$W_{\bar{i}|i}$ as in Figure 1. In particular, we assume that each packet
intended for $\mathsf{Rx}_{\bar{i}}$ becomes available to $\mathsf{Rx}_{i}$
according to a Bernoulli $\left(1-\epsilon_{i}\right)$ process distributed
independently from all other processes and the messages, and that

$\displaystyle
H\left(W_{\bar{i}|i}\right)=\left(1-\epsilon_{i}\right)H\left(W_{\bar{i}}\right),\qquad
i=1,2.$ (7)

######  Remark 2.

The assumptions we made 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_{i}[\ell],\qquad\ell=1,2,\ldots,nR_{i},$ (8)

where $W_{i}[\ell]$ is the $\ell^{\mathrm{th}}$ bit of message $W_{i}$, and
$E_{i}[\ell]$ is an i.i.d. Bernoulli $(1-\epsilon_{i})$ process independent of
all other channel parameters.

Transmitter’s knowledge of side-information: We consider the scenario in which
the transmitters know exactly what fraction of their own messages is available
to the unintended receiver. From the perspective of Remark 2, each transmitter
learns the side channel gains associated with its receiver.

Encoding: The constraint imposed at the encoding function $f_{i,t}(.)$ at time
index $t$ is given by:

$\displaystyle X_{i}[t]=f_{i,t}\left(W_{i},G^{t-1}\right),$ (9)

however, to highlight the transmitters’ knowledge of the available side-
information at the unintended receiver, we use the following notation:

$\displaystyle X_{i}[t]=f_{i,t}\left(W_{i},W_{i|\bar{i}},G^{t-1}\right),$ (10)

where we implicitly assume the knowledge of
$\delta_{1},\delta_{2},\epsilon_{1},$ and $\epsilon_{2}$ is available to each
transmitter as side-information.

Decoding: Each receiver $\mathsf{Rx}_{i}$, $i=1,2$, uses a decoding function
$\varphi_{i,n}\left(Y_{i}^{n},G^{n},W_{\bar{i}|i}\right)$ to get an estimate
$\widehat{W}_{i}$ of $W_{i}$. 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})],$ (11)

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 exist block encoders at the transmitters, and block decoders at the
receivers, such that $\lambda_{i,n}$ goes to zero as the block length $n$ goes
to infinity. The capacity region is the closure of the set of the achievable
rate pairs and is denoted by $\mathcal{C}$.

##  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 Outer-bounds

The following theorem establishes a new set of outer-bounds on the capacity
region of the two-user interference channel with altering topology and random
receiver cache.

######  Theorem 1 (Outer-bounds).

For the two-user interference channel with altering topology, delayed CSIT,
and random receiver cache as described in Section II, we have

$\mathcal{C}\subseteq\mathcal{C}^{\mathrm{out}}\equiv\left\\{\begin{array}[]{ll}0\leq
R_{i}\leq\left(1-\delta_{ii}\right),&i=1,2,\\\
0\leq\beta_{i}R_{i}+R_{\bar{i}}\leq\left(1-\delta_{{\sf
Rx}_{\bar{i}}}\right),&i=1,2.\end{array}\right.$ (12)

where

$\displaystyle\beta_{i}\overset{\triangle}{=}\frac{\epsilon_{\bar{i}}\left(1-\delta_{\bar{i}i}\right)}{\left(1-\delta_{{\sf
Tx}_{i}}\right)}.$ (13)

Before establishing the condition under which these bounds are achievable, we
provide some interpretations and insights into these converse bounds. First,
we re-write the bounds for when the channels are distributed independently
across users, and $\delta_{ij}=\delta,\epsilon_{i}=\epsilon$,
$i,j\in\\{1,2\\}$. In other words, we focus on the symmetric model with
independent links. Then, we can modify the region in (12) as

$\left\\{\begin{array}[]{ll}0\leq R_{i}\leq\left(1-\delta\right),&i=1,2,\\\
0\leq\frac{\epsilon}{1+\delta}R_{i}+R_{\bar{i}}\leq\left(1-\delta^{2}\right),&i=1,2.\end{array}\right.$
(14)

######  Remark 3.

From (14), we conclude that when $\epsilon\leq\delta(1+\delta)$, the region is
simply described by $0\leq R_{i}\leq\left(1-\delta\right)$. We note that this
latter expression describes the capacity of two parallel non-interfering
point-to-point erasure channels. To put into perspective, when $\delta=1/2$
and $\epsilon\leq 3/4$ (_i.e._ only $1/4$ of each message is available to the
unintended user), the outer-bound matches that of two non-interfering erasure
channels.

Figure 2: The new outer-bounds in (15) for $\epsilon\in\\{1,1/2,0\\}$ as well
as the parallel (non-interfering) sum-rate bound as a red dashed line. Note
that for convenience, the x-axis represents $(1-\delta)$, which the
probability of each link being active.

Figure 2 depicts the parallel (non-interfering) sum-rate bound of
$2(1-\delta)$ as well as the sum-rate outer-bound obtained by intersecting

$\displaystyle\frac{\epsilon}{1+\delta}R_{i}+R_{\bar{i}}\leq\left(1-\delta^{2}\right),\qquad
i=1,2,$ (15)

of (14). For convenience, the x-axis represents $(1-\delta)$, which the
probability of each link being active. As noted in Remark 3 (and also observed
in [9] for the no side-information scenario), depending on the value of
$\epsilon$ and $\delta$, the sum-rate might be dominated by either of these
bounds. For instance, for $\epsilon=1/2$, when
$(1-\delta)\leq(-1+\sqrt{3})/2$, the parallel erasure bounds are dominant and
when $(1-\delta)\geq(-1+\sqrt{3})/2$, the bounds in (15) are dominant. We also
note that $\epsilon=0$ corresponds to the scenario in which the entire message
of each user is available to the unintended user, and thus, $2(1-\delta)$ is
easily achievable. On the other end, $\epsilon=1$ is the scenario with no
side-information, and the results recover the region in [9] as expected.

Figure 3: The outer-bound region for $\delta=1/4$ and different values of
$\epsilon$.

Figure 3 depicts the outer-bound region for $\delta=1/4$ and different values
of $\epsilon$. The gray shaded region is the baseline with no side-information
($\epsilon=1$), and the hashed green region is the gain when $\epsilon=5/7$.
As we show in Theorem 2 and under the specified conditions, for
$5/7\leq\epsilon\leq 1$, we can achieve the outer-bounds and thus, the
capacity region is characterized. We further note that for
$\epsilon\leq\delta(1+\delta)=5/16$, the outer-bound region is simply
expressed by $R_{i}\leq(1-\delta)=3/4$.

###  III-B Achievable rates

In this section, we consider a specific subset of the interference channels
with altering topology in which a total of four topology configurations may
occur at any given time as summarized in Figure 4–Topology $A$, $B$, $C$, and
$D$, with respective probabilities:

$\displaystyle
p_{A}=(1-\delta)^{2},~{}p_{B}=\delta(1-\delta),~{}p_{C}=\delta(1-\delta),~{}p_{D}=\delta^{2},$
(16)

and we further assume $\epsilon_{1}=\epsilon_{2}=\epsilon$.

There are multiple reasons for choosing this specific channel distribution as
in general with four binary links, a total of $16$ channel realizations would
be possible as considered in [9]. However, including all cases would make
tracking the status of the previously transmitted signals more complicated;
while the four channel realizations of Figure 4 maintain the key technical
challenges and simplify the analysis. Second, the channel realizations of
Figure 4 have an interesting motivation from two-unicast networks with a group
of relays and the end-to-end network could be captured with these realizations
[28, 29, 14, 30].

Figure 4: For the inner-bounds, we assume the channel can only fall into one
of four configurations at any given time.

We note that the outer-bounds of Theorem 1 where derived for channels
distributed independently across time but not necessarily across users. Thus,
those outer-bounds hold for the channel we consider in this part as summarized
in Figure 4, and can be re-written as

$\left\\{\begin{array}[]{ll}0\leq R_{i}\leq\left(1-\delta\right),&i=1,2,\\\
0\leq\frac{\epsilon}{1+\delta}R_{i}+R_{\bar{i}}\leq\left(1-\delta^{2}\right),&i=1,2.\end{array}\right.$
(17)

The following theorem establishes the conditions under which the outer-bounds
of Theorem 1 are achievable.

######  Theorem 2 (Achievability Conditions).

For the two-user interference channel with altering topology, delayed CSIT,
and random receiver cache as described in Section II, we have

  1. 1.

Sum-Capacity: The maximum sum-rate outer-bound of Theorem 1, specialized in
(17) to the channel described above, is achievable when

$\displaystyle\epsilon\geq\frac{1}{1+\frac{(1-2\delta)^{+}}{1+\delta}}.$ (18)

  2. 2.

Capacity Region: The entire outer-bound region of Theorem 1, specialized in
(17) to the channel described above, is achievable when

$\displaystyle\epsilon\geq\max\left\\{\frac{1}{1+\frac{(1-2\delta)^{+}}{1+\delta}},\frac{\delta(1+\delta)}{(1-\delta)}\right\\}.$
(19)

First, we note that for $\delta>1/2$, the condition expressed in (18) implies
$\epsilon=1$, _i.e._ no side-information at the receivers, which is covered in
[9]. Thus, we focus on $\delta\leq 1/2$, and (18) becomes:

$\displaystyle\epsilon\geq\frac{1+\delta}{2-\delta},\quad\text{for~{}}\delta\leq\frac{1}{2}.$
(20)

We further note that (20) also implies that

$\displaystyle\epsilon\geq\delta(1+\delta),$ (21)

and based on the outer-bounds expressed in (14) and Remark 3, at the maximum
sum-rate point, we have

$\displaystyle
R_{i}=\frac{\left(1+\delta\right)\left(1-\delta^{2}\right)}{1+\delta+\epsilon}.$
(22)

Finally, if $\delta\leq(+3-\sqrt{5})/2\approx 0.382$ and the condition in (18)
is satisfied, then (19) also holds. In other words, for
$\delta\leq(+3-\sqrt{5})/2$ and $\epsilon$ satisfying (18), the capacity
region is characterized.

Figure 5: Sum-rate outer-bound for the symmetric channel of Figure 4 and the
region in which the outer-bound is achievable.

Figure 5 depicts the sum-rate outer-bound of Theorem 1, specialized in (17) to
the channel we study in this section, for $\epsilon=3/4$ and highlights the
region in which the sum-rate outer-bound is achievable based on Theorem 2.

##  IV Proof of Theorem 1: Deriving the outer-bounds

In this section, we derive the outer-bounds of Theorem 1. The derivation of
the outer-bounds on individual rates is straightforward, and thus, omitted. In
fact, it is well established that the capacity of a point-to-point erasure
channel with erasure probability $\delta_{i}$ is $\left(1-\delta_{i}\right)$.
In what follows, we derive

$\displaystyle\beta_{1}R_{1}+R_{2}\leq\left(1-\delta_{{\sf Rx}_{2}}\right),$
(23)

where as indicated in (13), we have

$\displaystyle\beta_{1}=\frac{\epsilon_{2}\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}.$ (24)

The derivation of the other bound would follow by simply changing user IDs
$1\leftrightarrow 2$.

Suppose rate-tupe $\left(R_{1},R_{2}\right)$ is achievable. We enhance
receiver $\mathsf{Rx}_{1}$ by providing the entire $W_{2}$ to it, as opposed
to $W_{2|1}$, and we note that this cannot reduce the rates. Then, we have

$\displaystyle n$
$\displaystyle\left(\beta_{1}R_{1}+R_{2}\right)=\beta_{1}H(W_{1})+H(W_{2})$
$\displaystyle\overset{(a)}{=}\beta_{1}\underbrace{H(W_{1}|W_{2},G^{n})}_{\mathrm{Enhanced}~{}{\sf
Rx}_{1}}+H(W_{2}|W_{1|2},G^{n})$
$\displaystyle\overset{(\mathrm{Fano})}{\leq}\beta_{1}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}H(Y_{1}^{n}|W_{2},G^{n})-\beta_{1}\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_{{\sf
Rx}_{2}}\right)+2\upxi_{n},$ (25)

where $\upxi_{n}\rightarrow 0$ as $n\rightarrow\infty$; $(a)$ follows from the
independence of the messages and the channels, and captures the enhancement of
receiver $\mathsf{Rx}_{1}$; $(b)$ follows from Theorem 3 below; $(c)$ is true
since the entropy of a binary random variable is at most one, and the receiver
is not in erasure a fraction $\left(1-\delta_{{\sf Rx}_{2}}\right)$ of the
communication time. Dividing both sides by $n$ and let $n\rightarrow\infty$,
we get (23).

######  Theorem 3.

For the two-user interference channel with altering topology, delayed CSIT,
and random receiver cache as described in Section II, and $\beta_{1}$ given in
(24), we have

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

where $\upxi_{n}\rightarrow 0$ as $n\rightarrow\infty$.

###### Proof.

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

$\displaystyle H\left(Y_{2}[t]|Y_{2}^{t-1},W_{1|2},W_{2},G^{n}\right)$
$\displaystyle\quad\overset{(a)}{=}H\left(Y_{2}[t]|Y_{2}^{t-1},W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(b)}{=}H\left(G_{21}[t]X_{1}[t]\oplus
G_{22}[t]X_{2}[t]|Y_{2}^{t-1},W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(c)}{=}H\left(G_{21}[t]X_{1}[t]\oplus
G_{22}[t]X_{2}[t]|Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad=H\left(G_{21}[t]X_{1}[t]|Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad=\left(1-\delta_{21}\right)H\left(X_{1}[t]|Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G_{21}[t]=1,G^{t-1}\right)$
$\displaystyle\quad\overset{(d)}{=}\left(1-\delta_{21}\right)H\left(X_{1}[t]|Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(e)}{\geq}\left(1-\delta_{21}\right)H\left(X_{1}[t]|Y_{1}^{t-1},Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(f)}{=}\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(G_{11}[t]X_{1}[t],G_{12}[t]X_{1}[t]|Y_{1}^{t-1},Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(g)}{=}\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}[t],Y_{2}[t]|Y_{1}^{t-1},Y_{2}^{t-1},X_{2}[t],W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(h)}{=}\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}[t],Y_{2}[t]|Y_{1}^{t-1},Y_{2}^{t-1},W_{1|2},W_{2},G^{t}\right)$
$\displaystyle\quad\overset{(i)}{=}\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}[t],Y_{2}[t]|Y_{1}^{t-1},Y_{2}^{t-1},W_{1|2},W_{2},G^{n}\right),$
(27)

where $(a)$ follows from the temporal independence of the channels and the
causal feedback structure; $(b)$ follows from the channel model of (3); $(c)$
holds since according to (9), we have:

$\displaystyle X_{2}[t]=f_{2,t}\left(W_{2},G^{t-1}\right);$ (28)

$(d)$ holds since according to the delayed CSIT assumption $X_{1}[t]$ is
independent of the channel realizations at time instant $t$; $(e)$ follows
from the fact that conditioning reduces entropy; $(f)$ comes from the fact
that $\Pr\left(G_{11}[t]=G_{21}[t]=0\right)=\delta_{{\sf Tx}_{1}}$; $(g)$
follows from the fact that $X_{2}[t]$ and $G[t]$ are in the condition; $(h)$
holds for the same reason as step $(c)$; and $(i)$ follows for the same reason
as step $(a)$.

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

$\displaystyle
H\left(Y_{2}^{n}|W_{1|2},W_{2},G^{n}\right)\geq\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}^{n},Y_{2}^{n}|W_{1|2},W_{2},G^{n}\right)$
$\displaystyle\quad\geq\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right).$ (29)

Now, for the final step, we note that

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

and

$\displaystyle H\left(W_{1}|Y_{1}^{n},W_{2},G^{n}\right)\leq n\upxi_{n}.$ (31)

Thus, from (30) and (31), we get

$\displaystyle H$ $\displaystyle\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right)\geq
H\left(\bar{W}_{1|2}\right)-n\upxi_{n}$
$\displaystyle\overset{\eqref{Eq:MessageSplitting}}{=}\epsilon_{2}H\left(W_{1}\right)-n\upxi_{n}\overset{(a)}{\geq}\epsilon_{2}H\left(Y_{1}^{n}|W_{2},S^{n}\right)-n\upxi_{n},$
(32)

where $\bar{W}_{1|2}$ is the complement of $W_{1|2}$ in $W_{1}$, and $(a)$ is
obtained from (30) 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 (IV) and (IV), we obtain

$\displaystyle H$
$\displaystyle\left(Y_{2}^{n}|W_{1|2},W_{2},G^{n}\right)\overset{\eqref{Eq:withSideInfo}}{\geq}\frac{\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}^{n}|W_{1|2},W_{2},G^{n}\right)$
$\displaystyle\overset{\eqref{Eq:RemovingSideInfo}}{\geq}\frac{\epsilon_{2}\left(1-\delta_{21}\right)}{\left(1-\delta_{{\sf
Tx}_{1}}\right)}H\left(Y_{1}^{n}|W_{2},G^{n}\right)-n\upxi_{n}$
$\displaystyle\overset{\eqref{Eq:Beta1_EICwCache}}{=}\beta_{1}H\left(Y_{1}^{n}|W_{2},G^{n}\right)-n\upxi_{n}.$
(33)

It is worth noting that a similar technique to what we used to obtain (IV) was
also used in [31]. This completes the proof of Theorem 3. ∎

##  V Proof of Theorem 2: Exploiting knowledge of
receiver side-information at the Transmitter

In this section, we provide the proof of Theorem 2, _i.e._ the achievability,
and we show that the achievable region matches the outer-bounds of Theorem 1
under the specified conditions. We first provide a motivating example and
then, present the detailed proof. We also note that in this section, for the
proofs and the motivating example, we assume the conditions and assumptions of
the theorem are satisfied, and later in Section V-C we provide some intuitions
for when these conditions are violated.

###  V-A Key ideas and motivating example

Key ideas: The power of wireless is in multicast. More specifically, gains are
magnified if we can satisfy multiple users simultaneously. This simple and
intuitive idea is behind most wireless communication algorithms. To see how
this idea can be used in interference channels with altering topology, delayed
CSIT, and random receiver cache, we first explain the network coding
opportunities, and then, present an example to explain the overall
achievability strategy.

Figure 6: The transmitted bits in these examples can be combined for efficient
multicast retransmission.

Suppose at some time instant $t_{1}$, network topology $A$ is realized,
meaning that all wireless links are active as in Figure 6(a). If bits $a$ and
$b$ were transmitted from $\mathsf{Tx}_{1}$ and $\mathsf{Tx}_{2}$,
respectively, then each receiver obtains a linear combination of these
bits111Note that if we assumed further continuous channel gains on top of the
binary coefficients, these equations would have been almost surely linearly
independent, which would be of value in general. However, by limiting
ourselves to binary coefficients, the two equations are identical and need to
make smart re-transmission choices in the future.. It seems that providing
only $a$ or $b$ to both receivers would be the optimal solution. However, we
show there are other opportunities that can improve the network throughput.
Suppose $c$ is part of $W_{1|2}$ (intended for $\mathsf{Rx}_{1}$ but in
$\mathsf{Rx}_{2}$’s cache) and $d$ is part of $W_{2|1}$. This scenario could
have also happened if at the time of transmitting $c$ and $d$, topology $B$
was realized as in Figure 6(b). This time, it seems $c$ and $d$ could be sent
to their respective receivers through two non-interfering point-to-point
erasure links as they are apriori known to the unintended receiver.
Interestingly, we can come up with a more efficient solution:
$\mathsf{Tx}_{1}$ should deliver $a\oplus c$ and $\mathsf{Tx}_{2}$ should
deliver $b\oplus d$ to both receivers. This way, $\mathsf{Rx}_{1}$ will end up
with $a\oplus b,d,a\oplus c$, and $b\oplus d$, from which, it can recover $a$
and $c$. A similar story goes for $\mathsf{Rx}_{2}$. In summary, we achieved
multicasting gains by mixing the signals available locally to each transmitter
rather than retransmitting individual ones.

Motivating example: To keep the description short and convey the main points,
for the motivating example, we focus on the maximum sum-rate point. We further
use expected values of random variables as opposed to a more careful analysis
involving concentration theorems and defer such analysis to the next
subsection where we present the complete proof. We further choose an example
where $\epsilon$ satisfies (18) of Theorem 2 with equality, which further
shortens the description of achievability. In particular, we assume

$\displaystyle\delta=\frac{1}{5},\epsilon=\frac{2}{3}.$ (34)

This scenario corresponds to strong point-to-point erasure links (success rate
of $4/5$) and when each receiver has apriori access to $1/3$ of the message of
the other user. For these parameters, the maximum sum-rate point using (17)
is:

$\displaystyle\left(R_{1},R_{2}\right)\approx\left(0.62,0.62\right).$ (35)

We start with $m$ bits for each receiver where $1/3m$ of the bits for each
receiver is apriori known to the unintended receiver. Each transmitter
separates its bits into two groups, the first are those known to the
unintended receiver, called the side-information bits, and the second would be
the complement of the first group. Each transmitter keeps sending out one bit
from the second group until the channel realization learned through the
feedback channel is _n_ ot topology $D$. This process on average takes

$\displaystyle\frac{\epsilon m}{1-\delta^{2}}.$ (36)

After this initial phase, each bit falls into three categories based on the
topology that was realized during its transmission (topology $A$, $B$, or
$C$). Those in topology $C$ are already delivered and no further action is
needed. For those in topologies $A$ and $B$, we can retransmit the combination
of them as discussed above. Further, for the choice of $\delta=1/5$, there
will be more bits associated with topology $A$ than $B$. We take advantage of
this and mix the remaining bits of topology $A$ with the side-information bits
at each transmitter, _i.e._ those known apriori to the unintended receiver
through the random cache. In this example, $\delta$ and $\epsilon$ were
carefully chosen such that the number of bits in topology $A$ was exactly
equal to those in topology $B$ and the random cache. The combined (XORed) bits
can be delivered at the multiple-access channel (MAC) capacity formed at each
receiver equal to $(1-\delta^{2})$. In summary, for this particular example,
the total communication time is given by

$\displaystyle t_{\mathrm{total}}=\underbrace{\frac{\epsilon
m}{1-\delta^{2}}}_{\text{initial~{}phase}}+\underbrace{\frac{\epsilon(1-\delta)^{2}m}{(1-\delta^{2})^{2}}}_{\text{multicasting~{}XORed~{}bits}}\approx
1.62,$ (37)

which combined with the fact that each transmitter had $m$ bits to deliver,
immediately implies the desired sum-rate.

###  V-B Proof of Theorem 2

As discussed earlier in Section III-B, we first note that if $\delta>1/2$,
then the condition in (18) alongside the fact that $0\leq\epsilon\leq 1$,
_i.e._

$\displaystyle\epsilon\geq\frac{1}{1+\frac{(1-2\delta)^{+}}{1+\delta}},$ (38)

is simply equivalent to $\epsilon=1$, or no side-information at either of the
receivers. This case falls under the results of [9]. Thus, in this section we
assume $\delta\leq 1/2$, and (18) becomes

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

Figure 7: The overall shape of the outer-bound region for $\delta\leq 1/2$ and
when (18) is satisfied.

For this setting, all outer-bounds in Theorem 1 are active and the region is
depicted in Figure 7. To prove Theorem 2, then it suffices to show the
achievability of the maximum sum-rate point, _i.e._

$\displaystyle\left(R_{1},R_{2}\right)=\left(\frac{(1+\delta)(1-\delta^{2})}{1+\delta+\epsilon},\frac{(1+\delta)(1-\delta^{2})}{1+\delta+\epsilon}\right),$
(40)

and either of the corner points (the other would follow due to symmetry),
_e.g._ ,

$\displaystyle\left(R_{1},R_{2}\right)=\left(\frac{\delta(1+\delta)}{\epsilon}(1-\delta),(1-\delta)\right).$
(41)

We remind the reader that according to Theorem 2, we can achieve this latter
corner-point when further (19) is satisfied.

####  V-B1 Maximum sum-rate point

We start with $m$ bits for each user out of which a fraction $(1-\epsilon)$ is
available to the unintended receiver for $\epsilon$ satisfying (39). As
mentioned earlier, we refer to the bits known apriori to the receivers as
“side-information” bits. The achievability strategy is divided into three
phases.

The first phase is uncoded, uncategorized transmission and each bit that is
not known apriori to the unintended receiver, is repeated until the channel
realization is not topology $D$ of Figure 4. In other words, each bit is
repeated as long as all channels are equal to $0$. After this phase, three
categories can be identified: delivered bits (topology $C$), side-information
bits (those in Topology $B$ and the ones known apriori to the transmission at
the receivers), and bits in topology $A$.

Phase 2 benefits from the idea described in Section V-A and XORs all the side-
information bits with those in topology $A$, and sends the resulting bits at
the multicast sum-rate of $(1-\delta^{2})$. As we show shortly, (39)
guarantees there will be more bits (on average) in topology $A$ than side-
information bits.

In Phase 3, the remaining bits in topology $A$ need to be delivered. However,
as mentioned in Section V-A, as there are no more network coding opportunities
available, it suffices to send half of these bits at the multicast sum-rate.
For example, in the scenario of Figure 6(a), delivering only $a$ or $b$ to
both receivers is sufficient for decoding. We note that if (39) holds with
equality, the communication ends after Phase 2 and Phase 3 is not needed.

Rate analysis: Phase 1 takes a total time of

$\displaystyle t_{\mathrm{P.1}}=\frac{\epsilon
m}{(1-\delta^{2})}+\mathcal{O}\left(m^{2/3}\right),$ (42)

where the big $O$ notation is used in its standard definition. The reason for
the addition of $\mathcal{O}\left(m^{2/3}\right)$ is ensure all bits are
communicated with probability approaching $1$ as $m\rightarrow\infty$. If at
the end of Phase 1, there are still some bits left for transmission at either
of the transmitters, we declare an error of type-I and terminate the
communication.

Upon completion of Phase 1, denote the (random) number of bits at transmitter
$\mathsf{Tx}_{i}$ in topology $A$ with $N_{i}^{A}$ and in topology $B$ with
$N_{i}^{B}$. If either of the following inequalities hold, we declare an error
of type-II and terminate the communication:

$\displaystyle
N_{i}^{A}<\frac{\Pr\left(\text{~{}topology~{}}A\right)}{1-\Pr\left(\text{~{}topology~{}}D\right)}\epsilon
m-\mathcal{O}\left(m^{2/3}\right)=\frac{(1-\delta)^{2}}{(1-\delta^{2})}\epsilon
m-\mathcal{O}\left(m^{2/3}\right),$ $\displaystyle
N_{i}^{B}<\frac{\Pr\left(\text{~{}topology~{}}B\right)}{1-\Pr\left(\text{~{}topology~{}}D\right)}\epsilon
m-\mathcal{O}\left(m^{2/3}\right)=\frac{\delta(1-\delta)}{(1-\delta^{2})}\epsilon
m-\mathcal{O}\left(m^{2/3}\right).$ (43)

Phase 2 takes a total time of

$\displaystyle
t_{\mathrm{P.2}}=\frac{2}{(1-\delta^{2})}\left(\underbrace{(1-\epsilon)m}_{\text{apriori~{}side~{}info.}}+\underbrace{\frac{\delta(1-\delta)\epsilon
m}{(1-\delta^{2})}}_{\text{Topology~{}B}}\right)+\mathcal{O}\left(m^{2/3}\right),$
(44)

and if upon termination of Phase 2, there are still some bits left for
transmission at either of the transmitters, we declare an error of type-I and
terminate the communication.

If (39) holds with equality, the communication ends after Phase 2 and Phase 3
is not needed. Phase 3 takes a total time of

$\displaystyle
t_{\mathrm{P.3}}=\frac{1}{(1-\delta^{2})}\left(\underbrace{\frac{(1-\delta)^{2}\epsilon
m}{(1-\delta^{2})}}_{\text{topology~{}}A}-\underbrace{(1-\epsilon)m}_{\text{apriori~{}side~{}info.}}-\underbrace{\frac{\delta(1-\delta)\epsilon
m}{(1-\delta^{2})}}_{\text{Topology~{}B}}\right)+\mathcal{O}\left(m^{2/3}\right),$
(45)

and if upon termination of Phase 3, there are still some bits left for
transmission at either of the transmitters, we declare an error of type-I and
terminate the communication.

Using Bernstein inequality [32], we can show that the probability of errors of
types I, II, and III decreases exponentially and approaches zero222In simple
terms this inequality states that if $X_{1},\ldots,X_{r}$ are $r$ independent
random variables, and $M=\sum_{i=1}^{r}{X_{i}}$, then
$Pr\left[|M-\mathbb{E}\left[M\right]|>\alpha\right]\leq
2\exp\left(\frac{-\alpha^{2}}{4\sum_{i=1}^{r}\mathrm{Var}\left(X_{i}\right)}\right)$.
as $m\rightarrow\infty$. In fact, throughout this section, we intentionally
picked $m^{\frac{2}{3}}$ to add to the constants in order to guarantee that
the error terms vanish as $m$ increases. For instance, to bound the
probability of error type-I, we have:

$\displaystyle\Pr\left[\mathrm{error~{}type\noindent-\noindent
I}\right]\overset{\text{Union~{}Bound}}{\leq}\sum_{i=1}^{2}{\Pr\left[Q_{i\rightarrow
i}\mathrm{~{}is~{}not~{}empty}\right]}$
$\displaystyle~{}=4\exp\left(\frac{-m^{4/3}}{4\left(1-\delta^{4}\right)\delta^{4}\left[\frac{1}{1-\delta^{2}}m+m^{\frac{2}{3}}\right]}\right),$
(46)

which decreases exponentially to zero as $m\rightarrow\infty$. We refer the
reader to [9] for a more detailed discussion on using Bernstein inequality
(and Chernoff-Hoeffding bound [33, 34]) to analyze the error probabilities.

The total communication time can be calculated as follows:

$\displaystyle
t_{\mathrm{total}}=t_{\mathrm{P.1}}+t_{\mathrm{P.2}}+t_{\mathrm{P.3}}=\frac{(1-\delta)}{(1-\delta^{2})^{2}}\left(1+\delta+\epsilon\right)m+\mathcal{O}\left(m^{2/3}\right),$
(47)

and as we started with a total of $2m$ bits, the maximum sum-rate corner-point
given in (40) is achieved when $m\rightarrow\infty$.

####  V-B2 Maximum sum-rate when $R_{2}=(1-\delta)$

For this corner-point, based on the rates given in (41), we start with $m$
bits for $\mathsf{Tx}_{2}$, and

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

bits for $\mathsf{Tx}_{1}$, where based on the choice parameters described in
this section, as shown in (21), we have $m_{1}<m$. This section will also
demonstrate the challenges in achieving the outer-bounds when rates are
unequal. The main idea is for $\mathsf{Tx}_{1}$ to be responsible for
interference management, while $\mathsf{Tx}_{2}$ communicates at the maximum
possible rate.

In Phase 1, $\epsilon m_{1}$ bits from each transmitter will be communicated
similar to the maximum sum-rate case. In Phase 2, $\mathsf{Tx}_{2}$ will
finish communicating the remainder of the bits that are not known apriori to
$\mathsf{Tx}_{1}$, meanwhile, $\mathsf{Tx}_{1}$ delivers a portion of the bits
that fell under topology $A$ in Phase 1 at a low enough rate,
$\delta(1-\delta)$, such that both receivers can decode them. This way,
$\mathsf{Tx}_{1}$ helps with interference management as $\mathsf{Tx}_{2}$
continues its communications. In Phase 3, $\mathsf{Tx}_{2}$ communicates the
side-information bits (those known to $\mathsf{Tx}_{1}$), and meanwhile
$\mathsf{Tx}_{1}$ encodes the remaining bits of topology $A$ at
$\delta(1-\delta)$, its side-information bits at $(1-\delta)^{2}$, and sends
the superposition of the resulting encoded bits. Figure 8 pictorially
summarizes the achievability strategy for this corner-point.

Figure 8: A summary of the achievability strategy for the maximum sum-rate
when $R_{2}=(1-\delta)$.

Rate analysis: For simplicity, we eliminate the
$\mathcal{O}\left(m^{2/3}\right)$ terms and the error analysis as they follow
the same steps as the previous case. Phase 1 takes (on average) a total time
of

$\displaystyle t_{\mathrm{P.1}}=\frac{\epsilon
m_{1}}{(1-\delta^{2})}\overset{\eqref{Eq:m1-EIC}}{=}\frac{\delta}{(1-\delta)}m.$
(49)

It is helpful to view Phases 2 and 3 from the perspective of
$\mathsf{Tx}_{1}$. Essentially, during these two phases, $\mathsf{Tx}_{1}$
needs to deliver all its bits that fell under topology $A$ at a rate of
$\delta(1-\delta)$. This rate captures when each receiver observes only the
signal of $\mathsf{Tx}_{1}$. We will describe the decoding at each receiver is
detail shortly, but based on the discussion, we have:

$\displaystyle
t_{\mathrm{P.2}}+t_{\mathrm{P.3}}=\frac{1}{\delta(1-\delta)}\times\frac{(1-\delta)^{2}\epsilon
m_{1}}{(1-\delta^{2})}=m,$ (50)

which would result in:

$\displaystyle
t_{\mathrm{total}}=t_{\mathrm{P.1}}+t_{\mathrm{P.2}}+t_{\mathrm{P.3}}\overset{\eqref{Eq:m1-EIC}}{=}\frac{m}{(1-\delta)}.$
(51)

Given that $\mathsf{Tx}_{2}$ has $m$ bits and $\mathsf{Tx}_{1}$ has $m_{1}$
bits, given in (48), (assuming successful delivery which will be discussed
below) the rates in (41) will be achieved for $m\rightarrow\infty$.

To show decodability of all bits, we first note that all the bits of
$\mathsf{Tx}_{1}$ that fell under topology $A$ in Phase 1 are decodable at
both receivers given the chosen rate of $\delta(1-\delta)$. In other words,
$\mathsf{Tx}_{2}$ will never retransmit any of its bits under topology $A$ as
it must deliver its bits at maximum point-to-point rate of $(1-\delta)$. In
particular, during Phase 2, we can assume $\mathsf{Rx}_{2}$ does not receive
any interference as it can decode and subtract the contribution from
$\mathsf{Tx}_{1}$.

Phase 3 is dedicated to the delivery of the side-information bits of
$\mathsf{Tx}_{2}$, which will not cause any interference at $\mathsf{Rx}_{1}$,
and meanwhile, $\mathsf{Tx}_{1}$ sends the superposition of the bits in
topology $A$ and its side-information bits. The side-information bits do not
cause any interference at $\mathsf{Rx}_{2}$, and the bits under topology $A$
are decodable at both receivers as discussed earlier. Thus, in Phase 3, we can
assume interference-free transmission for both users. Phase 3 takes on
average:

$\displaystyle
t_{\mathrm{P.3}}=\frac{1}{(1-\delta)}\left(1-\frac{\epsilon}{(1+\delta)}\right),$
(52)

and as long as this time is sufficient for the delivery of the side-
information bits of $\mathsf{Tx}_{1}$ at rate $(1-\delta)^{2}$, the
decodability is guaranteed.

The average number of the side-information bits at $\mathsf{Tx}_{1}$ is:

$\displaystyle\frac{\delta\left(1+\delta-\epsilon\right)}{\epsilon},$ (53)

which at rate $(1-\delta)^{2}$, takes:

$\displaystyle\frac{\delta\left(1+\delta-\epsilon\right)}{\epsilon(1-\delta)^{2}}$
(54)

times to deliver. Thus, for this time to be less than or equal to
$t_{\mathrm{P.3}}$, we require:

$\displaystyle\frac{\delta\left(1+\delta-\epsilon\right)}{\epsilon(1-\delta)^{2}}\leq
t_{\mathrm{P.3}},$ (55)

which in turn is equivalent to:

$\displaystyle\epsilon\geq\frac{\delta(1+\delta)}{(1-\delta)}.$ (56)

This last inequality is what was required in Theorem 2 beyond (39) to
guarantee the entire region would be achievable. Thus, the proof is completed.

###  V-C Discussion: when the conditions of Theorem 2 are violated

To better understand the challenges when the conditions of Theorem 2 are
violated, we provide an example in this section in which $\delta=1/2$ and
$\epsilon=3/4$ (_i.e._ only $1/4$ of each message is available to the
unintended user). For these values, the outer-bound region of Theorem 1 is
equivalent to $R_{i}\leq 1/2$, $i=1,2$. If these bounds are tight, the
transmitters should be able to effectively eliminate all interference at the
unintended users and achieve a sum-rate of $1$.

We focus on the maximum sum-rate and start with $m$ bits at each transmitter,
out of which $1/4$ are side-information bits. The challenge is after the
initial phase, as the four realizations in Figure 4 are equiprobable for
$\delta=1/2$, the number of bits under topology $B$ equals that of the bits in
topology $A$. Thus, after combining the bits, the side-information bits cannot
be combined with any other bits and should be sent at the maximum point-to-
point rate (_i.e._ losing the multicast gain). The overall communication time
for this example is given by:

$\displaystyle
t_{\mathrm{total}}=\underbrace{\frac{1}{1-.5^{2}}\times\frac{3m}{4}}_{\text{Phase~{}1}}+\underbrace{\frac{1}{1-.5^{2}}\times\frac{.5^{2}}{1-.5^{2}}\times\frac{3m}{4}}_{\text{Phase~{}2~{}multicast}}+\underbrace{\frac{2}{1-.5}\times\frac{1m}{4}}_{\text{Phase~{}3~{}point-
to-point}}=\frac{9m}{4}.$ (57)

Thus, the achievable sum-rate is equal to $8/9$, which is below the sum-rate
of $1$ the outer-bounds suggest. Rather surprisingly, this rate is even below
the scenario with no side-information ($\delta=1/2$ and $\epsilon=1$) for
which achievability of a sum-rate of $9/10$ was already derived in [9]. In
other words, in this particular example for our achievability scheme, it is
better to ignore the side-information, suggesting that the inner-bounds need
improvement. However, it seems no further linear coding opportunities are
available to the transmitters. Therefore, it might be the case that to achieve
the outer-bounds, one may need to exploit non-linear codes.

##  VI Conclusion

In this paper, we studied the benefit of having random receiver cache in
interference channels with altering topology and delayed feedback. We provided
a new set of outer-bounds based on a key theorem that quantifies the baseline
entropy available to each receiver under the specific assumptions of the
problem. We showed that these bounds are tight under certain conditions, thus,
characterizing the capacity region in such cases. We further discussed how the
inner and the outer bounds behave when these conditions are violated. The next
steps include investigating whether non-linear coding may improve the inner-
bounds or the outer-bounds need improvement when the capacity remains open.
Further, it would interesting to understand the implications of random
receiver cache on latency and age of information in interference channels with
altering topology.

## 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] A. Sengupta, R. Tandon, and O. Simeone, “Fog-aided wireless networks for content delivery: Fundamental latency tradeoffs,” IEEE Transactions on Information Theory, vol. 63, no. 10, pp. 6650–6678, 2017.
  * [4] J. Hachem, U. Niesen, and S. N. Diggavi, “Degrees of freedom of cache-aided wireless interference networks,” IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 5359–5380, 2018.
  * [5] J. Zhang and P. Elia, “Fundamental limits of cache-aided wireless bc: Interplay of coded-caching and csit feedback,” IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 3142–3160, 2017.
  * [6] S. P. Shariatpanahi, G. Caire, and B. H. Khalaj, “Multi-antenna coded caching,” in 2017 IEEE International Symposium on Information Theory (ISIT), pp. 2113–2117, IEEE, 2017.
  * [7] A. Vahid, M. A. Maddah-Ali, and A. S. Avestimehr, “Interference channel with binary fading: Effect of delayed network state information,” in 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 894–901, IEEE, 2011.
  * [8] A. Vahid, M. A. Maddah-Ali, and A. S. Avestimehr, “Binary fading interference channel with delayed feedback,” in 2012 IEEE International Symposium on Information Theory Proceedings, pp. 1882–1886, IEEE, 2012.
  * [9] 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.
  * [10] 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.
  * [11] S. Mishra, I.-H. Wang, and S. N. Diggavi, “Harnessing bursty interference in multicarrier systems with output feedback,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4430–4452, 2017.
  * [12] 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.
  * [13] H. Sun, C. Geng, S. Jafar, et al., “Topological interference management with alternating connectivity,” in International Symposium on Information Theory Proceedings (ISIT), pp. 399–403, IEEE, 2013.
  * [14] I. Issa, S. L. Fong, and A. S. Avestimehr, “Two-hop interference channels: Impact of linear schemes,” IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5463–5489, 2015.
  * [15] A. Vahid and R. Calderbank, “When does spatial correlation add value to delayed channel state information?,” in 2016 IEEE International Symposium on Information Theory (ISIT), pp. 2624–2628, IEEE, 2016.
  * [16] 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.
  * [17] A. Vahid and R. Calderbank, “Impact of local delayed CSIT on the capacity region of the two-user interference channel,” in 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2421–2425, IEEE, 2015\.
  * [18] A. Vahid and R. Calderbank, “Two-user erasure interference channels with local delayed CSIT,” IEEE Transactions on Information Theory, vol. 62, no. 9, pp. 4910–4923, 2016.
  * [19] A. Vahid, M. A. Maddah-Ali, A. S. Avestimehr, and Y. Zhu, “Binary fading interference channel with no CSIT,” IEEE Transactions on Information Theory, vol. 63, no. 6, pp. 3565–3578, 2017.
  * [20] P.-H. Lin, E. A. Jorswieck, and B. Matthiesen, “On fast fading binary interference channels without channel state information at the transmitter,” in 2020 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 1–6, IEEE, 2020.
  * [21] P.-H. Lin, E. A. Jorswieck, R. F. Schaefer, M. Mittelbach, and C. R. Janda, “New capacity results for fading gaussian multiuser channels with statistical csit,” IEEE Transactions on Communications, 2020.
  * [22] R. H. Etkin, D. N. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” IEEE Transactions on Information Theory, vol. 54, no. 12, pp. 5534–5562, 2008.
  * [23] S. Nassirpour and A. Vahid, “Throughput, delay, and complexity tradeoffs in interference channels,” in 2020 10th Annual Computing and Communication Workshop and Conference (CCWC), pp. 0348–0354, IEEE, 2020.
  * [24] R. Kassab, O. Simeone, A. Munari, and F. Clazzer, “Space diversity-based grant-free random access for critical and non-critical IoT services,” in ICC 2020-2020 IEEE International Conference on Communications (ICC), pp. 1–6, IEEE, 2020.
  * [25] R. Kassab, A. Munari, F. Clazzer, and O. Simeone, “Uncoordinated grant-free radio access via diversity for critical and non-critical IoT services,” arXiv preprint arXiv:2003.09257, 2020.
  * [26] A. Vahid and A. S. Avestimehr, “The two-user deterministic interference channel with rate-limited feedback,” Proceedings of the IEEE International Symposium on Information Theory (ISIT), July 2010.
  * [27] A. Vahid, C. Suh, and A. S. Avestimehr, “Interference channels with rate-limited feedback,” IEEE Transactions on Information Theory, vol. 58, no. 5, pp. 2788–2812, 2012.
  * [28] I. Shomorony and A. S. Avestimehr, “Two-unicast wireless networks: Characterizing the degrees of freedom,” IEEE Transactions on Information Theory, vol. 59, no. 1, pp. 353–383, 2012.
  * [29] A. Vahid, I. Shomorony, and R. Calderbank, “Informational bottlenecks in two-unicast wireless networks with delayed CSIT,” in 53rd Annual Allerton Conference on Communication, Control, and Computing, pp. 1256–1263, IEEE, 2015.
  * [30] A. Vahid, “On the degrees-of-freedom of two-unicast wireless networks with delayed CSIT,” IEEE Transactions on Information Theory, vol. 65, no. 8, pp. 5176–5188, 2019.
  * [31] 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.
  * [32] S. Bernstein, “On a modification of chebyshev’s inequality and of the error formula of laplace,” Ann. Sci. Inst. Sav. Ukraine, Sect. Math, vol. 1, no. 4, pp. 38–49, 1924.
  * [33] J. Phillips, “Chernoff-hoeffding inequality and applications,” arXiv preprint arXiv:1209.6396, 2012.
  * [34] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol. 58, no. 301, pp. 13–30, 1963.