Near Optimal Coded Data Shuffling for Distributed Learning
Mohamed Adel Attia

Ravi Tandon

arXiv:1801.01875v1 [cs.IT] 5 Jan 2018

Department of Electrical and Computer Engineering
University of Arizona, Tucson, AZ, USA.
E-mail: {madel, tandonr}@email.arizona.edu
January 8, 2018

Abstract
Data shuffling between distributed cluster of nodes is one of the critical steps in implementing
large-scale learning algorithms. Randomly shuffling the data-set among a cluster of workers
allows different nodes to obtain fresh data assignments at each learning epoch. This process has
been shown to provide improvements in the learning process. However, the statistical benefits
of distributed data shuffling come at the cost of extra communication overhead from the master
node to worker nodes, and can act as one of the major bottlenecks in the overall time for
computation. There has been significant recent interest in devising approaches to minimize
this communication overhead. One approach is to provision for extra storage at the computing
nodes. The other emerging approach is to leverage coded communication to minimize the overall
communication overhead.
The focus of this work is to understand the fundamental trade-off between the amount of
storage and the communication overhead for distributed data shuffling. In this work, we first
present an information theoretic formulation for the data shuffling problem, accounting for the
underlying problem parameters (number of workers, K, number of data points, N , and the
available storage, S per node). We then present an information theoretic lower bound on the
communication overhead for data shuffling as a function of these parameters. We next present
a novel coded communication scheme and show that the resulting communication overhead of
K
the proposed scheme is within a multiplicative factor of at most K−1
from the informationtheoretic lower bound. Furthermore, we present the aligned coded shuffling scheme for some
storage values, which achieves the optimal storage vs communication trade-off for K < 5, and
K− 1
further reduces the maximum multiplicative gap down to K−13 , for K ≥ 5.

This work was supported by the NSF Grant CAREER-1651492.

1

Introduction

Owing to the parallelized nature of the distributed computing, and the abundance of computational
resources over a large cluster of workers, distributed computational frameworks can enable dataintensive learning tasks and big data applications in a timely manner. Distributed computing
comes at the unavoidable communication cost due to data transfer to the distributed machines,
and the data shuffling process among the distributed workers, which is a basic building block in
machine learning paradigms. The data shuffling block can arise in many applications such as: a)
random shuffling of the data-set across different points before each learning epoch so that each
worker is assigned new training data, which is a common practice that provides statistical benefits,
e.g., distributed gradient descent algorithm and its stochastic variations [1–3]; b) shuffling the
data-set across attributes to assign different features (or attributes) to each worker, e.g., in mobile
cloud gaming systems [4]; and c) shuffling the data between the mappers and the reducers in the
MapReduce framework [5], where the reducers are interested in collecting the data with the assigned
“key(s)” from the mappers.
Another limiting byproduct of distributing the learning process over a large number of machines
is the latency caused by the stragglers, i.e., the workers slower than the average due to several factors
such as resource contention, disk failure, power limits, and heterogeneous processing capabilities
[6, 7]. The straggler problem usually limits the completion time by the slowest worker. Several
approaches to mitigate the stragglers effect include a) scheduling redundant computations in [8–11],
such that any unexpected tardiness or failure of a worker can be compensated by another worker
doing the same computations; b) work stealing where the faster workers once they finish their tasks
take over the remaining computations from the slower workers [12]; and recently c) work exchange
based on the work conservation principle, where coarse heterogenity knowledge/estimation can be
used to reassign the work load according to the speed of the workers [13].
A promising research has recently emerged in large scale distributed computing addressing both
wired networks, where the computations are done over the cloud [14, 15], and wireless networks,
where the computations are done over small mobile machines removing the burden from the cloud
[16–18]. Distributed computing platforms can also be classified according to the underlying network
topology. In the master-worker setting, a centralized master node posses the whole data set and
assigns different parts of the data to a set of distributed workers, which collaboratively learn a
shared prediction model to be averaged out at the master node later; while in the worker-to-worker
setting (also referred to as the MapReduce framework [5]), the distributed workers are mapped to
train different parts of the data to calculate some functions, then the reducers collects the data
with the same “key” to compute each function separately.
The application of coding theory to overcome the communication and latency bottlenecks in
order to speed-up the learning process was first considered in [19]. In particular, the idea of using
coded data shuffling was first proposed in [19], where excess storage at the workers was utilized
to create coded broadcasting opportunities in order to reduce the communication overhead. In
the same work, (n, k) Maximum Distance Separable (MDS) codes were proposed for distributed
matrix multiplication to mitigate the impact of stragglers. Coded computation using MDS codes in
2

presence of stragglers was proposed in [20] for synchronous gradient descent, and [21–23] for linear
computation tasks, e.g., matrix multiplication. The use of Polynomial codes for high dimensional
coded matrix multiplication was proposed in [24]. Coded computation over wireless networks was
proposed in [25], where only one worker can transmit at a time. The use of codes to reduce the
communication overhead due to data shuffling was considered in [26–35]. In [26–29], the authors
considered the MapReduce setting, where in order to reduce the communication between the mappers and the reducers, coding opportunities are created with more redundant computations at the
mappers, leading to a trade-off between communication and computation. [30,31] provided a unified
coding framework for distributed computing, where the communication load due to shuffling can
be alleviated by trading the computational complexity in the presence of straggling servers. The
information theoretic limits for data shuffling in the wired master-worker setting was considered
in [19,32,33]. Coded data shuffling in wireless setting was recently considered in [18,34,35] for both
centralized and decentralized approaches.
Related Works on Data Shuffling and Connections to Index Coding: Using codes for random data shuffling over wired master-worker based distributed computational systems was first
considered in [19]. A probabilistic coding scheme was introduced showing how using excess storage
can reduce the average communication overhead. In our initial preliminary work [32], the optimal
worst-case communication overhead was characterized as a function of the available storage for
K = 2, 3 workers using a systematic storage placement, and data delivery schemes. In another
work [33], the no-excess storage case was considered, where it was shown that even for minimum
storage value coding opportunities still exist. A systematic coding scheme was developed for any
number of workers, which was proven to be information theoretically optimal in the worst-case
scenario.
The data shuffling problem can also be viewed as an index coding problem [36], where the
amount of data stored at the workers form the side information, and the new data assignments
are the messages needed by each worker. The side information in the data shuffling problem is
generally not static, where the storage of the workers can be adapted to reduce the communication
overhead in the next shuffle. We propose in this work a structural invariant placement mechanism,
where the storage of the workers is updated according to the latest shuffle to maintain the structure.
Furthermore, it was shown in [36] that the index coding is a NP-hard problem, and may require
in the worst-case a rate of order O(K), where K is the number of workers. A pliable index coding
approach for data shuffling was assumed in [37], where a semi-random shuffles were considered and
was shown to achieve a rate of order O(log2 (K)). In this work however, we consider the worst-case
rate over all possible shuffles and show that even for the minimum storage (side information at the
workers), a rate of order O( K−1
K ) can be achieved, which does not scale with the number of workers
for large values of K.

1.1

Main Contributions of this Paper

In this paper, we focus on the coded data shuffling for the wired master-worker setting, where
coding opportunities are created by exploiting the excess storage at the workers. Before each

3

learning epoch, the data is shuffled at the master node for different training data assignment at
each worker, which causes the communication overhead. On one extreme, when all the workers
have enough storage to store the whole data set, then no communication is needed for any random
shuffle. On the other hand, when the storage is just enough to store the assigned data, which we also
refer to as the no excess storage case, then the communication is expected to be maximal. Thus,
we aim to characterize the fundamental information-theoretic trade-off between the communication
overhead due to shuffling and the available storage at the distributed workers. The contributions
of this paper are summarized next:
• We first derive an information theoretic lower bound on the worst-case communication overhead
for the data shuffling problem. We start by obtaining a family of lower bounds on the rate of some
chosen shuffles. Since the rate of any shuffle is at most as large as the worst-case shuffle, the
obtained lower bounds serve as valid lower bounds for the worst-case rate as well. We then average
out all the lower bounds we get using the chosen shuffles. The key step here is choosing the shuffles
which lead to the best lower bound on the communication overhead as a function of the storage.
In particular, we consider a set of cyclic shuffles where no overlap between the assigned data batch
to any worker in the two subsequent shuffles. Based on a novel bounding methodology similar to
the recent results in the caching literature [38, 39], we are able to express the lower bound as a
linear program (LP). We then solve the LP to obtain the best lower bounds on the communication
overhead for different regimes of storage.
• Next, we introduce our achievable scheme based on a placement/update procedure that maintains the structure of the storage, which we refer to as “the structural invariant placement and
update”. The storage placement involves partitioning the data points across dimensions, which
allows each worker to store at least some parts of each data point. Through a careful novel storage update, the structure of the storage can be maintained over time. This allows for applying a
data delivery mechanism similar to [40], which approaches the optimal worst-case communicationK
as the
storage trade-off (based on the obtained lower bound) within a vanishing gap ratio of K−1
number of distributed workers K increases.
• Finally, we introduce new ideas on how to fully characterize the optimal worst-case communication overhead. We show that by considering more sophisticated interference alignment mechanisms,
we can force the interference seen by each worker to occupy the minimum possible dimensions. We
refer to this procedure as the “Aligned Coded Shuffling” scheme. This scheme also involves a different structural invariant update mechanism of the storage, which is based one data partitioning
and relabeling over time. Following these ideas, we can close the gap between the obtained bounds
for some storage values, which closes the gap for K < 5, and brings the maximum gap ratio down
K− 1
to K−13 , for K ≥ 5.

2

System Model

We assume a master node which has access to the entire data-set A = {D1 , D2 , . . . , DN } of size
N d bits, i.e., A is a set containing N data points, denoted by D1 , D2 , . . . , DN , where d is the
dimensionality of each data point. Treating the data points Dn as i.i.d. random variables, we
4

therefore have the entropies of these random variables as
H(A) = N × H(Dn ) = N d,

∀n ∈ {1, 2, . . . , N }.

(1)

At each iteration, indexed by t, the master node divides the data-set A into K data batches
given as At (1), At (2), . . . , At (K), where At (k) denotes the data partition designated to be processed
by worker wk at time t, and these batches correspond to the random permutation of the data-set,
π t : A → (At (1), . . . , At (K)). Note that these data batches are disjoint, and span the whole
data-set, i.e.,
At (i) ∩ At (j) = φ,

∀i 6= j,

At (1) ∪ At (2) ∪ . . . ∪ At (K) = A,

(2a)
∀t.

(2b)

Hence, the entropy of any batch At (k) is given as
H(At (k)) =

N
1
H(A) = d,
K
K

∀k ∈ {1, . . . , K}.

(3)

After getting the data batch, each worker locally computes a function (as an example, this
function could correspond to the gradient or sub-gradients of the data points assigned to the
worker). The local functions from the K workers are processed subsequently at the master node.
We assume that each worker wk has a storage Zkt of size Sd bits, for a real number S, which is used
to store some function of the data-set. Therefore, if we consider Zkt as a random variable then,
H(Zkt |A) = 0,

∀k ∈ [1 : K].

(4)

For processing purposes, the assigned data blocks are needed to be stored by the workers, therefore,
each worker wk must at least store the data block At (k) at time t, which gives the storage constraint
as
H(Zkt ) = Sd ≥ H(At (k)),

∀k ∈ {1, . . . , K}.

According to (3) and (5), we get the minimum storage per worker S ≥
processing constraint as
H(At (k)|Zkt ) = 0, ∀k ∈ {1, . . . , K},

(5)
N
K.

We also have the
(6)

which means At (k) is a deterministic function of the storage Zkt .
In the next epoch t + 1, the data-set is randomly reshuffled at the master node according
to a random permutation π t+1 : A → (At+1 (1), At+1 (2), . . . , At+1 (K)), which also satisfies the
properties in (2). The main communication bottleneck occurs during Data Delivery since the
master node needs to communicate the new data batches to the workers. Trivially, if the storage
(per worker) exceeds N d bits, i.e., S ≥ N , then each worker can store the whole data-set, and no
communication has to be done between the master node and the workers for any shuffle. Therefore
from the constraint on minimum storage per worker, we can write the possible range for storage as
5

N
K

≤ S ≤ N.
We next proceed to describe the data delivery mechanism, and the associated encoding and
decoding functions. The main process can be divided into two phases, namely the data delivery
phase and the storage update phase as described next:

2.1

Data Delivery Phase

At time t + 1, the master node sends a function of the data batches for the subsequent shuffles
(πt , πt+1 ), Xπt ,πt+1 = φ(At (1), . . . , At (K), At+1 (1), . . . , At+1 (K)) = φπt ,πt+1 (A) over the shared
link, where φ is the data delivery encoding function,
h N i2K
φ : 2K d
→ [2Rπt ,πt+1 d ],

(7)

where Rπt ,πt+1 is the rate of the shared link based on the shuffles (πt , πt+1 ). Therefore, we have

H Xπt ,πt+1 |A = 0,


H Xπt ,πt+1 = Rπt ,πt+1 d,

(8)

which means that Xπt ,πt+1 is a deterministic function of the whole data-set A.
Each worker wk should reliably decode the desired batch At+1 (k) out of the transmitted function
Xπt ,πt+1 , as well as the data stored in the previous time slot Zkt , i.e., At+1 (k) = ψ(Xπt ,πt+1 , Zkt ),
where ψ is the decoding function at the workers,
N

ψ : [2Rπt ,πt+1 d ] × [2Sd ] → [2 K d ].

(9)

Therefore, for reliable decoding, we have the following decodability constraint at each worker:

H At+1 (k)|Zkt , Xπt ,πt+1 = 0,

2.2

∀k ∈ {1, . . . , K}.

(10)

Storage Update Phase

At the next iteration t + 1, every worker updates its stored content according to the placement
strategy, where the new storage content for worker wk is given by Zkt+1 , which is a function of the
old storage content Zkt as well as transmitted function Xπt ,πt+1 , i.e., Zkt+1 = µ(Xπt ,πt+1 , Zkt ), where
µ is the update function
µ : [2Rπt ,πt+1 d ] × [2Sd ] → [2Sd ],
(11)
Therefore, we have the following storage-update constraint:
H(Zkt+1 |Zkt , Xπt ,πt+1 ) = 0,

∀k ∈ {1, . . . , K}.

(12)


N
d bits, can be used to store
The excess storage after storing At+1 (k) in Zkt+1 , given by S − K
opportunistically a function of the remaining K − 1 data batches. For the scope of this work, we
assume that the placement of the excess storage is uncoded, which means that the excess storage
is dedicated to store uncoded functions of the remaining K − 1 batches. We give the notation
6

At+1 (i, k), where i 6= k, as the part of data that worker wk stores about At+1 (i) in the excess
storage at time t + 1. As a result, we can write the content of Zkt+1 for uncoded storage placement
as


t+1
t+1
t+1
Zk = A (k),
∪ A (j, k) .
(13)
j∈[1:K]\k

Furthermore, we assume a generic placement strategy for the excess storage as follows: the batch
[1:K]\i , where 2[1:K]\i is the power set
At+1 (i) consists of 2K−1 partitions, denoted as At+1
W (i), W ∈ 2
of all possible subsets of the set [1 : K] \ i including the empty set. The worker wk , for k 6= i, stores
t+1 (i), and
the partition At+1
W (i) in the excess storage, only if k ∈ W. Therefore, the sub-batches A
At+1 (i, k) can be expressed as
At+1 (i) =

∪

W⊆[1:K]\i

At+1
W (i),

At+1 (i, k) =

∪

W⊆[1:K]\i: k∈W

At+1
W (i).

(14)

t+1
t+1
Let us consider At+1
W (i) as a random variable with entropy H(AW (i)) = |AW (i)|d, and size
|At+1
W (i)| normalized by the data point size d. Therefore, the following two constraints are obtained:
• Data size constraint: The first constraint is related to the total size of the data given by N d
bits,
K

N=

K

1X
1
(a) 1 X
H(A) =
H(At+1 (i)) =
d
d
d
i=1

=

K X
K
X

X

H(At+1
W (i))

i=1 W⊆[1:K]\i

X

`=1 i=1 W⊆[1:K]\i: |W|=`

|At+1
W (i)|

=

K
X

x` ,

(15)

`=1

where (a) follows from (14), and x` ≥ 0 is defined as
∆

x` =

K
X

X

i=1 W⊆[1:K]\i: |W|=`

|AtW (i)|,

` ∈ [0 : K − 1].

(16)

• Excess storage size constraint: The second constraint is related to the total excess storage

N
d bits,
of all the workers, which cannot exceed K S − K


K
N
1X
≥
K S−
K
d

X

i=1 k∈[1:K]\i

(b)

=

K
X

X

i=1 W⊆[1:K]\i

H A

t+1

K
 (a) X
(i, k) =

|W| |At+1
W (i)| =

X

X

i=1 k∈[1:K]\i W⊆[1:K]\i: k∈W

K
K
X
X
`
`=1

X

i=1 W⊆[1:K]\i: |W|=t|

|At+1
W (i)|
(c)

|At+1
W (i)| =

K
X

`x` ,

(17)

`=1

where (a) follows from (14), (b) is true because when we sum up the contents of the excess storage
at all the workers, the chunk At+1
W (i) is counted |W| number of times, which is the number of
workers storing this chunk, and (c) follows from (16).
We next define the worst-case communication as follows:
7

Definition 1 (Worst-Case Communication) For any achievable scheme characterized by the
encoding, decoding, and cache update functions (φ, ψ, µ), the worst-case communication overhead
over all possible consecutive data shuffles (πt , πt+1 ) is defined as
(φ,ψ,µ)

∆

Rworst-case (S) =

(φ,ψ,µ)

max R(πt ,πt+1 ) (S).

(πt ,πt+1 )

(18)

∗
Our goal in this work is to characterize the optimal worst-case communication Rworst-case
(K, N, S)
defined as
∆
(φ,ψ,µ)
∗
Rworst-case
(S) = min Rworst-case (S).
(19)
(φ,ψ,µ)

∗
We next present a claim which shows that the optimal worst-case communication Rworst-case
(S) is
a convex function of the storage S:
∗
Claim 1 Rworst-case
(S) is a convex function of S, where S is the available storage at each worker.

Proof: Claim 1 follows from a simple memory sharing argument which shows that for any two
∗
∗
(S2 )) are achievable
(S1 )), and (S2 , Rworst-case
available storage values S1 and S2 , if (S1 , Rworst-case
optimal schemes, then for any storage S̄ = αS1 + (1 − α)S2 , 0 ≤ α ≤ 1, there is a scheme which
∗
∗
(S2 ).
(S1 ) + (1 − α)Rworst-case
achieves a communication overhead of R̄(S̄) = αRworst-case
This is done as follows: first, we divide the data-set A across d dimensions into 2 batches
namely; A(α) , and A(1−α) of dimensions αd, and (1 − α)d, for each point respectively. Then, we
(α)
(1−α)
divide the storage for every worker wk into 2 parts namely; Zk , and Zk
of size S1 αd, and
S2 (1 − α)d, respectively. The former batch A(α) will be shuffled among the former part of the
(α)
∗
storage Zk to achieve the point (S1 , Rworst-case
(S1 )), while the latter batch A(1−α) will be shuffled
(1−α)
∗
among the latter part of the storage Zk
to achieve the point (S2 , Rworst-case
(S2 )). Therefore,
the total achievable load is given by
∗
∗
H(X) = Rworst-case
(S1 )αd + Rworst-case
(S2 )(1 − α)d = R̄(S̄)d.

(20)

∗
(S̄) is upper bounded by R̄(S̄), the
We next note that the optimal communication rate Rworst-case
rate of the memory sharing scheme, i.e.,
∗
∗
∗
Rworst-case
(αS1 + (1 − α)S2 ) ≤ αRworst-case
(S1 ) + (1 − α)Rworst-case
(S2 ),

(21)

∗
which shows that Rworst-case
(S) is a convex function of S. 

2.3

Notation

The notation [n1 : n2 ] for n1 < n2 , and n1 , n2 ∈ N represents the set of all integers between n1 ,

n!
and n2 , i.e., [n1 : n2 ] = {n1 , n1 + 1, . . . , n2 }. The combination coefficient nk = (n−k)!k!
equals zero
for k > n, or k < 0. In order to describe subsets of ordered sets, we use the subscript to give
the indexes of the elements being chosen from the set, e.g., for the ordered set π = (π1 . . . , πn ),
π[1:4] = (π1 , π2 , π3 , π4 ). We denote Random Variables (RVs) by capital letters, ordered sets of RVs
8

by capital bold letters, and sets of data points/sub-points by calligraphy letters. The set in the
subscript of a set of ordered RVs is used for short notation of a subset of the set of RVs, e.g., for a
set of RVs Z = {Z1 , . . . , Zn }, we use ZW to denote the set {Zi }i∈W .
For a data-set A, we use the notation At (i) to denote the data partition assigned to the worker
wi at iteration t, At (i, j), for i 6= j, to denote the part of At (i) which is stored in the excess storage
of the worker wj at iteration t, while Atj (i), for i 6= j, to denote the part of At (i) which is only stored
in excess storage of the worker wj at iteration t, i.e., Atj (i) = At (i, j)\∪k6∈{i,j} At (i, k). The notation
At (W) is used to denote the union of the data partitions assigned to the workers at iteration t whose
indexes are in the set W, i.e., At (W) = ∪i∈W At (i). Similarly we have, At (W, j) = ∪i∈W At (i, j),
where j 6∈ W, and At (i, W) = ∪j∈W At (i, j), where i 6∈ W. The notation AtW (i), where i 6∈ W,
denotes a subset of At (i) which is exclusively and jointly stored at iteration t in the excess storage
of all the workers whose indexes are in the set W, i.e., AtW (i) = ∩j∈W At (i, j) \ ∪j6∈(W∪i) At (i, j).
The following table summarizes the notation used to denote the subsets of the data-set A:
Notation

Description

At (i)

The data partition assigned to wi at iteration t.

-

At (i, j), i 6= j

A subset of At (i) stored in the excess storage of wj at iteration t.

-

Atj (i), i 6= j

A subset of At (i) stored only in the excess
storage of wj at iteration t.

At (i, j) \ ∪k6∈{i,j} At (i, k)

At (W)

The union of the data partitions assigned
to every wi at iteration t, where i ∈ W.

∪i∈W At (i)

At (W, j),
At (i, W), i 6∈ W
AtW (i), i 6∈ W

3

Representation

The union of the sets At (i, j) for i ∈ W.
j 6∈ W
The union of the sets At (i, j) for j ∈ W.

A subset of At (i) which is exclusively and
jointly stored in the excess storage at iteration t of all the workers whose indexes are
in the set W.

∪i∈W At (i, j)
∪j∈W At (i, j)

∩j∈W At (i, j) \ ∪j6∈(W∪i) At (i, j)

Main Results and Discussions

The first theorem presents an achievable worst-case rate Rworst-case , which also yields an upper
∗
bound on the optimal storage-rate trade-off Rworst-case
.
Theorem 1 For a data-set containing N ∈ N data points, and a set of K ∈ N distributed workers,
the lower convex envelope of the following K + 1 storage-rate pairs is achievable:





K −1 N
N (K − i)
upper
, Rworst-case =
S = 1+i
,
K
K
K(i + 1)

9

∀i ∈ [0 : K].

(22)

Rworst-case
4

3

2
3
2

1
2
3
1
4

1
3

1

7
4

2

5
2

3 13
4

4

S

∗
for N = 4, and
Figure 1: The lower bound and the upper bound on the worst-case rate Rworst-case
K = 4 versus the amount of storage S. The maximum gap appears to be when S = 1, which is
given as a ratio 4/3.

The proof of Theorem 1 is presented in Appendix A. We present an encoding, decoding, and cache
update scheme, which achieves the above rate-storage pairs. One of the crucial steps in the proof is
the structural invariant placement and update of the storage of the workers over time. The storage
placement involves partitioning the data points across dimensions, which allows each worker to
store at least some parts of each data point, which in turns introduces a local storage gain for
any potential data assignment. In order to increase the global gain through increasing the coding
opportunities, we minimize the overlap between the parts stored by each worker of each data point.
Through a careful novel update of storage across time, the structure can be maintained for any
random data assignment, which allows applying a coded data delivery mechanism to reduce the
communication overhead. Now, we give the following illustrative example for K = N = 4 to
introduce the main elements of the achievability proof.
Example 1 Consider the case of K = 4 workers, and N = 4 i.i.d. data points, labeled as
{D1 , D2 , D3 , D4 }. According to Theorem 1, the achievable worst-case storage-rate trade-off is
given by the lower convex envelope of the 5 storage-rate pairs (S = 3i/4 + 1, R = (4 − i)/(i + 1))
for i ∈ [0 : 4], which is also shown by the red curve in Figure 1. From Claim 1, once we achieve
these pairs, the lower convex envelope is also achievable by memory sharing. At time t, we consider
the data is assigned according to the shuffle πt = (1, 2, 3, 4), e.g., w1 is assigned the data point D1 ,
i.e., At (1) = D1 . At time t + 1, we consider the cyclic shuffle πt+1 = (2, 3, 4, 1), e.g., w1 is assigned
the data point D2 at time t + 1, i.e., At+1 (1) = D2 . Once we achieve the rate for the shuffle
πt+1 = (2, 3, 4, 1), a similar data delivery mechanism can be used for any πt+1 ∈ [4!], where [4!] is
the set containing all the 4! possible permutations of the set [1 : 4]. The achievability, according to
10

(a)

Cache placement at time t
processing

At (1) D1,{1} D1,{2} D1,{3} D1,{4}
D2,{1}

D3,{1}

At (2) D2,{1} D2,{2} D2,{3} D2,{4}

D4,{1}

D1,{2}

At (2, 1) At (3, 1) At (4, 1)

D3,{2}

D4,{2}

D1,{3}

At (1, 2) At (3, 2) At (4, 2)

Storage at w1

At (4) D4,{1} D4,{2} D4,{3} D4,{4}

At (3) D3,{1} D3,{2} D3,{3} D3,{4}
D2,{3}

D1,{4}

D4,{3}

At (1, 3) At (2, 3) At (4, 3)

Storage at w2

D2,{4}

D3,{4}

At (1, 4) At (2, 4) At (3, 4)

Storage at w3

Storage at w4

excess
storage

(b)

Data Delivery and Cache Update at time t + 1
⇢
D2,{2} D3,{1} , D2,{3} D4,{1} , D2,{4} D1,{1} ,
X⇡t ,⇡t+1 =
D3,{3} D4,{2} , D3,{4} D1,{2} , D4,{4} D1,{3}
processing
At+1 (1) D2,{1} D2,{2} D2,{3} D2,{4}

D3,{1}

D4,{1}

D1,{1}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

Storage at w1

At+1 (2) D3,{1} D3,{2} D3,{3} D3,{4}

D2,{2}

D4,{2}

At+1 (3) D4,{1} D4,{2} D4,{3} D4,{4}

D2,{3}

D1,{2}

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

D3,{3}

At+1 (4) D1,{1} D1,{2} D1,{3} D1,{4}

D1,{3}

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

Storage at w2

Storage at w3

D2,{4}

D3,{4}

D4,{4}

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w4

excess
storage

Figure 2: Structural Invariant Storage placement, (a), and update, (b), for K = 4 workers, N = 4
data points, and i = 1 (S = 7/4). Every data point is partitioned into 4 sub-points each labeled by
a unique subset of the set [1 : 4] of length 1. Above the dotted line is the data point fully stored for
processing, and below the dotted line is the excess storage used to store the sub-points containing
the worker’s index.

(πt , πt+1 ), for the storage value S = 3i/4 + 1 and i ∈ [0 : 4] follows next.
• Case i = 0 (S = 1):
This storage value represents the no-excess storage case, where every worker only stores the
assigned data point under processing. To satisfy the new assignment at time t + 1, we choose now
to send the 4 data points, which satisfies any shuffle at time t+1, achieving the pair (S = 1, R = 4).
Later in Section D, we will show how to improve this rate and prove that in fact (S = 1, R = 3)
is optimal. The storage update is trivial in this case, where every worker keeps the new assigned
data point and discard the remaining three points.
• Case i = 1 (S = 7/4):
Storage Placement: The storage placement for i = 1 is shown in Figure 2a. First, every data point
is partitioned into 4 sub-points of size d/4 bits each, where every sub-point is labeled by a unique
subset W ⊆ [1 : 4] of size |W| = 1. For instance, the data point D1 is partitioned as follows:
D1 = {D1,{1} , D1,{2} , D1,{3} , D1,{4} }.

(23)

Every worker first fully stores the assigned data point. For the excess storage, every worker wk
stores from the remaining points, not being processed, the sub-points where k ∈ W. For instance,
w1 stores 1 sub-point of D2 , labeled as At (2, 1) = {D2,{1} }. To summarize, each worker stores the
assigned data point of size d, and for each one of the remaining 3 data points, it stores 1 sub-point
of size d/4. That is, the storage requirement is given by S = 1 + 3 × 1/4 = 7/4, which satisfies the
storage constraint for i = 1 (S = 7/4).
Data Delivery: According to the storage placement at time t in Figure 2a, at time t+1 every worker
11

needs 3 sub-points of the assigned data point, and every sub-point is available at least in one of the
remaining workers, e.g., w1 needs the sub-points {D2,{2} , D2,{3} , D2,{4} }. Now, if we pick any 2 out
of the 4 workers, then each one of the 2 workers needs a sub-point available at the other worker.
Therefore, we can send an “order 2” symbol, of size d/4 bits, useful for these chosen two workers in

the same time, and for all possible choices of 2 out of the 4 workers we send the following 42 = 6
coded symbols which satisfies the required 3 needed sub-points for the 4 workers:





D2,{2} ⊕ D3,{1} , useful for w1 , w2 , 










D2,{3} ⊕ D4,{1} , useful for w1 , w3 , 








D

2,{4} ⊕ D1,{1} , useful for w1 , w4 ,
Xπt ,πt+1 =
.
(24)
D


⊕ D4,{2} , useful for w2 , w3 , 
3,{3}











D
⊕
D
,
useful
for
w
,
w
,
2
4 
3,{4}
1,{2}








D
⊕D
, useful for w3 , w4 
4,{4}

1,{3}


The rate of this transmission is 42 /4 = 3/2, and the pair (S = 7/4, R = 3/2) is achieved.
Storage Update: At time t + 1, the storage update follows from Figure 2b. In order to maintain
the structure of the storage, the workers first store the data points newly assigned and acquired
from the delivery phase. For the excess storage update, each worker wk keeps from the data point
previously assigned at time t the sub-points which are labeled by a set W where k ∈ W. For
example, w1 keeps from At (1) = At+1 (4) = D1 the sub-point At+1 (4, 1) = {D1,{1} }.
• Case i = 2 (S = 5/2):
Storage Placement: The storage placement for i = 2 is shown in Figure 3a. First, every data point
is partitioned into 6 sub-points of size d/6 bits each, where every sub-point is labeled by a unique
subset W ⊆ [1 : 4] of size |W| = 2. For instance, the data point D1 is partitioned as follows:
D1 = {D1,{1,2} , D1,{1,3} , D1,{1,4} , D1,{2,3} , D1,{2,4} , D1,{3,4} }.

(25)

Every worker first fully stores the assigned data point. For the excess storage, every worker wk stores
from the remaining points, not being processed, the sub-points where k ∈ W. For instance, w1 stores
3 sub-point of D2 , labeled as At (2, 1) = {D2,{1,2} , D2,{1,3} , D2,{1,4} }. To summarize, each worker
stores the assigned data point of size d, and for each one of the remaining 3 data points, it stores 3
sub-point of size d/6 each. That is, the storage requirement is given by S = 1 + 3 × 3 × 1/6 = 5/2,
which satisfies the storage constraint for i = 2 (S = 5/2).
Data Delivery: According to the storage placement at time t in Figure 3a, at time t+1 every worker
needs 3 sub-points of the assigned data point, and every sub-point is available at least in two of the
remaining workers, e.g., w1 needs the sub-points {D2,{2,3} , D2,{2,4} , D2,{3,4} }. Now, if we pick any
3 out of the 4 workers, then every one of the 3 workers needs a sub-point available at the other 2
workers. Therefore, we can send an order 3 symbol, of size d/6 bits, useful for these chosen workers

in the same time, and for all possible choices of 3 out of the 4 workers we send the following 43 = 4
12

(a)
At (1)

D1,{1,2} D1,{1,3} D1,{1,4}
D1,{2,3} D1,{2,4} D1,{3,4}

At (2)

D2,{1,2} D2,{1,3} D2,{1,4}
D2,{2,3} D2,{2,4} D2,{3,4}

At (3)

D3,{1,2} D3,{1,3} D3,{1,4}
D3,{2,3} D3,{2,4} D3,{3,4}

At (4)

D4,{1,2} D4,{1,3} D4,{1,4}

D1,{1,2} D3,{1,2} D4,{1,2}

D1,{1,3} D2,{1,3} D4,{1,3}

D1,{1,4} D2,{1,4} D3,{1,4}

D2,{1,3} D3,{1,3} D4,{1,3}

D1,{2,3} D3,{2,3} D4,{2,3}

D1,{2,3} D2,{2,3} D4,{2,3}

D1,{2,4} D2,{2,4} D3,{2,4}

D2,{1,4} D3,{1,4} D4,{1,4}

D1,{2,4} D3,{2,4} D4,{2,4}

D1,{3,4} D2,{3,4} D4,{3,4}

D1,{3,4} D2,{3,4} D3,{3,4}

At (2, 1) At (3, 1) At (4, 1)

At (1, 2) At (3, 2) At (4, 2)

At (1, 3) At (2, 3) At (4, 3)

At (1, 4) At (2, 4) At (3, 4)

Storage at w2

(b)
X⇡t ,⇡t+1 =

D2,{1,2} D2,{1,3} D2,{1,4}
D2,{2,3} D2,{2,4} D2,{3,4}

At+1 (2)

Storage at w3

excess
storage

Storage at w4

Data Delivery and Cache Update at time t + 1
⇢

D2,{2,3}
D2,{3,4}

D3,{1,3}
D4,{1,4}

D3,{1,2} D3,{1,3} D3,{1,4}
D3,{2,3} D3,{2,4} D3,{3,4}

D4,{1,2} , D2,{2,4}
D1,{1,3} , D3,{3,4}
At+1 (3)

D3,{1,4}
D4,{2,4}

D4,{1,2} D4,{1,3} D4,{1,4}
D4,{2,3} D4,{2,4} D4,{3,4}

D1,{1,2} ,
D1,{2,3}

At+1 (4)

D1,{1,2} D1,{1,3} D1,{1,4}

D2,{1,2} D4,{1,2} D1,{1,2}

D2,{1,3} D3,{1,3} D1,{1,3}

D2,{1,4} D3,{1,4} D4,{1,4}

D3,{1,3} D4,{1,3} D1,{1,3}

D2,{2,3} D4,{2,3} D1,{2,3}

D2,{2,3} D3,{2,3} D1,{2,3}

D2,{2,4} D3,{2,4} D4,{2,4}

D3,{1,4} D4,{1,4} D1,{1,4}

D2,{2,4} D4,{2,4} D1,{2,4}

D2,{3,4} D3,{3,4} D1,{3,4}

D2,{3,4} D3,{3,4} D4,{3,4}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w2

Storage at w3

processing

D1,{2,3} D1,{2,4} D1,{3,4}

D3,{1,2} D4,{1,2} D1,{1,2}

Storage at w1

processing

D4,{2,3} D4,{2,4} D4,{3,4}

D2,{1,2} D3,{1,2} D4,{1,2}

Storage at w1

At+1 (1)

Cache placement at time t

excess
storage

Storage at w4

Figure 3: Structural Invariant Storage placement, (a), and update, (b), for K = 4 workers, N = 4
data points, and i = 2 (S = 5/2). Every data point is partitioned into 6 sub-points each labeled by
a unique subset of the set [1 : 4] of length 2. Above the dotted line is the data point fully stored for
processing, and below the dotted line is the excess storage used to store the sub-points containing
the worker’s index.

coded symbols which satisfies the required 3 needed sub-points for the 4 workers:





D
⊕
D
⊕
D
,
useful
for
w
,
w
,
w
,
1
2
3 
2,{2,3}
3,{1,3}
4,{1,2}








D

⊕
D
⊕
D
,
useful
for
w
,
w
,
w
,
1
2
4
2,{2,4}
3,{1,4}
1,{1,2}
Xπt ,πt+1 =
.




D
⊕
D
⊕
D
,
useful
for
w
,
w
,
w
,
1
3
4
2,{3,4}
4,{1,4}
1,{1,3}








D
⊕D
⊕D
, useful for w2 , w3 , w4 
3,{3,4}

4,{2,4}

(26)

1,{2,3}

 
The rate of this transmission is 43 / 42 = 2/3, and the pair (S = 5/2, R = 2/3) is achieved.
Storage Update: At time t + 1, the storage update follows from Figure 3b. In order to maintain the
structure of the storage, the workers first store the data points newly assigned and acquired from the
delivery phase. For the excess storage update, each worker wk keeps from the data point previously
assigned at time t the sub-points which are labeled by a set W where k ∈ W. For example, w1
keeps from At (1) = At+1 (4) = D1 the sub-point At+1 (4, 1) = {D1,{1,2} , D1,{1,3} , D1,{1,4} }.
• Case i = 3 (S = 13/4):
Storage Placement: The storage placement for i = 3 is shown in Figure 4a. First, every data point
is partitioned into 4 sub-points of size d/4 bits each, where every sub-point is labeled by a unique

13

(a)
At (1)

D1,{1,2,3}

D1,{1,2,4}

D1,{1,3,4}

D1,{2,3,4}

At (2)

Cache placement at time t

D2,{1,2,3}

D2,{1,2,4}

D2,{1,3,4}

D2,{2,3,4}

At (3)

D3,{1,2,3}

D3,{1,2,4}

D3,{1,3,4}

D3,{2,3,4}

At (4)

D4,{1,2,3}

D4,{1,2,4}

D4,{1,3,4}

D4,{2,3,4}

D2,{1,2,3} D3,{1,2,3} D4,{1,2,3}

D1,{1,2,3} D3,{1,2,3} D4,{1,2,3}

D1,{1,2,3} D2,{1,2,3} D4,{1,2,3}

D1,{1,2,4} D2,{1,2,4} D3,{1,2,4}

D2,{1,2,4} D3,{1,2,4} D4,{1,2,4}

D1,{1,2,4} D3,{1,2,4} D4,{1,2,4}

D1,{1,3,4} D2,{1,3,4} D4,{1,3,4}

D1,{1,3,4} D2,{1,3,4} D3,{1,3,4}

D2,{1,3,4} D3,{1,3,4} D4,{1,3,4}

D1,{1,3,4} D3,{1,3,4} D4,{1,3,4}

D1,{2,3,4} D2,{2,3,4} D4,{2,3,4}

D1,{2,3,4} D2,{2,3,4} D3,{2,3,4}

At (2, 1)

At (1, 2)

At (1, 3)

At (1, 4)

At (3, 1)

At (4, 1)

Storage at w1

At (3, 2)

(b)

D2,{1,2,3}

D2,{1,2,4}

D2,{1,3,4}

D2,{2,3,4}

At+1 (2)

At (2, 3)

At (4, 3)

Storage at w3

At (2, 4)

At (3, 4)

Storage at w4

D2,{2,3,4}

D3,{1,2,3}

D3,{1,2,4}

D3,{1,3,4}

D3,{2,3,4}

D3,{1,3,4}
At+1 (3)

D4,{1,2,4}

D4,{1,2,3}

D4,{1,2,4}

D4,{1,3,4}

D4,{2,3,4}

D1,{1,2,3}
At+1 (4)

D1,{1,2,3}

D1,{1,2,4}

D1,{1,3,4}

D1,{2,3,4}

D3,{1,2,3} D4,{1,2,3} D1,{1,2,3}

D2,{1,2,3} D4,{1,2,3} D1,{1,2,3}

D2,{1,2,3} D3,{1,2,3} D1,{1,2,3}

D2,{1,2,4} D3,{1,2,4} D4,{1,2,4}

D3,{1,2,4} D4,{1,2,4} D1,{1,2,4}

D2,{1,2,4} D4,{1,2,4} D1,{1,2,4}

D2,{1,3,4} D3,{1,3,4} D1,{1,3,4}

D2,{1,3,4} D3,{1,3,4} D4,{1,3,4}

D3,{1,3,4} D4,{1,3,4} D1,{1,3,4}

D2,{1,3,4} D4,{1,3,4} D1,{1,3,4}

D2,{2,3,4} D3,{2,3,4} D1,{2,3,4}

D2,{2,3,4} D3,{2,3,4} D4,{2,3,4}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w1

excess
storage

Data Delivery and Cache Update at time t + 1

X⇡t ,⇡t+1 =
At+1 (1)

At (4, 2)

Storage at w2

processing

Storage at w2

Storage at w3

processing

excess
storage

Storage at w4

Figure 4: Structural Invariant Storage placement, (a), and update, (b), for K = 4 workers, N = 4
data points, and i = 3 (S = 13/4). Every data point is partitioned into 4 sub-points each labeled
by a unique subset of the set [1 : 4] of length 3. Above the dotted line is the data point fully
stored for processing, and below the dotted line is the excess storage used to store the sub-points
containing the worker’s index.

subset W ⊆ [1 : 4] of size |W| = 3. For instance, the data point D1 is partitioned as follows:
D1 = D1 = {D1,{1,2,3} , D1,{1,2,4} , D1,{1,3,4} , D1,{2,3,4} }.

(27)

Every worker first fully stores the assigned data point. For the excess storage, every worker wk stores
from the remaining points, not being processed, the sub-points where k ∈ W. For instance, w1 stores
3 sub-point of D2 , labeled as At (2, 1) = {D2,{1,2,3} , D2,{2,2,4} , D2,{1,3,4} }. To summarize, each worker
stores the assigned data point of size d, and for each one of the remaining 3 data points, it stores 3
sub-point of size d/4 each. That is, the storage requirement is given by S = 1 + 3 × 3 × 1/4 = 13/4,
which satisfies the storage constraint for i = 3 (S = 13/4).
Data Delivery: According to the storage placement at time t in Figure 4a, at time t+1 every worker
only needs one sub-point of the assigned data point which is available at the three remaining workers,
e.g., w1 needs D2,{2,3,4} which is available at the workers w2 , w3 , and w4 . Therefore, we can send
the following order 4 symbol useful for all the 4 workers at the same time:
Xπt ,πt+1 = {D2,{2,3,4} ⊕ D3,{1,3,4} ⊕ D4,{1,2,4} ⊕ D1,{1,2,3} }.
Since the the size of each sub-point is d/4, the rate of the transmission is
the pair (S = 13/4, R = 1/4) is achieved.
14



4
4

(28)
/4 = 1/4 and hence

Storage Update: At time t + 1, the storage update follows from Figure 4b. In order to maintain the
structure of the storage, the workers first store the data points newly assigned and acquired from the
delivery phase. For the excess storage update, each worker wk keeps from the data point previously
assigned at time t the sub-points which are labeled by a set W where k ∈ W. For example, w1
keeps from At (1) = At+1 (4) = D1 the sub-point At+1 (4, 1) = {D1,{1,2,3} , D1,{2,2,4} , D1,{1,3,4} }.
• Case i = 4 (S = 4): This case is trivial where every worker can store all the 4 data points and
hence no communication is needed for any shuffle. Therefore, the pair (S = 4, R = 0) is achieved.
We next present our second main result in Theorem 2, which gives an information theoretic
lower bound on the optimal worst-case rate.
Theorem 2 For a data-set containing N ∈ N data points, and a set of K ∈ N distributed workers,
∗
a lower bound on Rworst-case
is given by the lower convex envelope of the following K storage-rate
pairs:


N (K − m)
N
lower
,
S = m , Rworst-case =
K
Km

∀m ∈ [1 : K].

(29)

The complete proof of Theorem 2 can be found in Appendix B.
Remark 1 (Basic idea for the converse) A lower bound over the optimal rate Rπ∗ t ,πt+1 of a
shuffle (πt , πt+1 ) serves also as a lower bound on the worst-case since the optimal worst-case rate
∗
is larger than the optimal rate for any shuffle, i.e., Rworst-case
≥ Rπ∗ t ,πt+1 . Therefore, we get lower
∗
bounds over Rworst-case
by focusing on a sequence of shuffles, and then average out all the lower
bounds. The novel part in our proof is to carefully choose the right shuffles which lead to the best
lower bound.
In our converse proof, we apply a novel bounding methodology similar to the recent result in [38,39],
where the optimal uncoded cache placement problem for a file delivery system is considered. In this
paper however, we consider the data delivery based on subsequent assignments according to random
shuffles of the data. Our problem also requires storing the data under processing, and allows for
storage update over time as opposed to [38, 39]. At the end, we arrive at a linear program subject
to the problem constraints (data size and storage constraints), which can be solved to obtain the
best lower bounds over different regimes of the available storage. In the following example, we show
how to obtain the lower bounds on the worst-case rate for the case of N = K = 4.
Example 2 Consider the case of K = 4 workers, and N = 4 i.i.d. data points, labeled as
{D1 , D2 , D3 , D4 }. Assume the 4 data points are assigned at time t according to πt = (1, 2, 3, 4),
i.e., At (k) = Dk for k ∈ [1 : 4]. Therefore, at time t, the data point Dk is fully stored at the cache
of the worker wk , and partially stored at the remaining workers, which gives the storage content of
the worker wk as follows:


t+1
Zk = Dk , ∪ Dj (k) ,
(30)
j∈[1:4]\k

15

where Dj (k) is the part of Dj stored in the excess storage of worker wk at time t.
Following Remark 1, we start by considering the following shuffle (πt , πt+1 ): for a permutation
σ : (1, 2, 3, 4) → (σ1 , σ2 , σ3 , σ4 ), the worker wσk is assigned at time t + 1 the data point that was
assigned to the worker wσk−1 at time t, i.e., At+1 (σk ) = At (σk−1 ) = Dσk−1 . Using the decodability
constraint in (10), worker wσk must be able to decode At+1 (σk ) = Dσk−1 using its own cache Zσt k
as well as the transmission X(πt ,πt+1 ) which gives the following condition:
H(At+1 (σk )|Zσt k , X(πt ,πt+1 ) ) = H(Dσk−1 |Zσt k , X(πt ,πt+1 ) ) = 0,

∀k ∈ [1 : 4].

(31)

Furthermore, from (6), each worker should store the assigned data point at time t, therefore,
H(At (σk )|Zσt k ) = H(Dσk |Zσt k ) = 0,

∀k ∈ [1 : 4].

(32)

Consequently, the transmission Xπt ,πt+1 as well as the cache of any three workers can decode the 4
data points, which can be shown as follows:
H(A|Zσt [2:4] , X(πt ,πt+1 ) ) = H(D1 , D2 , D3 , D4 |Zσt [2:4] , X(πt ,πt+1 ) )
= H(Dσ1 , Dσ2 , Dσ3 , Dσ4 |Zσt [2:4] , X(πt ,πt+1 ) )
(a)

(b)

≤ H(Dσ1 |Zσt 2 , X(πt ,πt+1 ) ) + H(Dσ2 |Zσt 2 ) + H(Dσ3 |Zσt 3 ) + H(Dσ4 |Zσt 4 ) = 0, (33)

where (a) follows from the fact that H(A, B) ≤ H(A) + H(B) and that conditioning reduces
entropy, and (b) follows directly using (31) and (32). Next, we obtain the following bound using
(33):
4d = H(A) = I(A; Ztσ[2:4] , Xπt ,πt+1 ) + H(A|Ztσ[2:4] , Xπt ,πt+1 )
(a)

(b)

≤ H(Ztσ[2:4] , Xπt ,πt+1 ) = H(Zσt 4 , Xπt ,πt+1 ) + H(Zσt 2 , Zσt 3 |Zσt 4 , Xπt ,πt+1 )

≤ H(Xπt ,πt+1 ) + H(Zσt 4 ) + H(Zσt 3 |Zσt 4 , Xπt ,πt+1 ) + H(Zσt 2 |Zσt 3 , Zσt 4 , Xπt ,πt+1 )
(c)

≤ Rπ∗ t ,πt+1 d + H(Zσt 4 ) + H(Zσt 3 |Zσt 4 , Dσ3 , Dσ4 ) + H(Zσt 2 |Zσt 3 , Zσt 4 , Dσ2 , Dσ3 , Dσ4 )

(d)

= Rπ∗ t ,πt+1 d + H(Dσ4 , Dσ1 (σ4 ), Dσ2 (σ4 ), Dσ3 (σ4 )) + H(Dσ1 (σ3 ), Dσ2 (σ3 )|Zσt 4 )
+ H(Dσ1 (σ2 )|Zσt 3 , Zσt 4 )

(e)

= Rπ∗ t ,πt+1 d + H(Dσ4 , Dσ1 (σ4 ), Dσ2 (σ4 ), Dσ3 (σ4 )) + H(Dσ1 (σ3 ), Dσ2 (σ3 )|Dσ1 (σ4 ), Dσ2 (σ4 ))
+ H(Dσ1 (σ2 )|Dσ1 (σ3 ), Dσ1 (σ4 ))

= Rπ∗ t ,πt+1 d + H(Dσ4 ) + [H(Dσ1 (σ4 )) + H(Dσ1 (σ3 )|Dσ1 (σ4 )) + H(Dσ1 (σ2 )|Dσ1 (σ3 ), Dσ1 (σ4 ))]
+ [H(Dσ2 (σ4 )) + H(Dσ2 (σ3 )|Dσ2 (σ4 ))] + H(Dσ3 (σ4 ))
(f )

= Rπ∗ t ,πt+1 d + d + H(Dσ1 (σ2 , σ3 , σ4 )) + H(Dσ2 (σ3 , σ4 )) + H(Dσ3 (σ4 ))

(g)

∗
≤ Rworst-case
d + d + H(Dσ1 (σ2 , σ3 , σ4 )) + H(Dσ2 (σ3 , σ4 )) + H(Dσ3 (σ4 )),

16

(34)

where (a) follows from (33), (4), and (8), where Ztσ[2:4] , and Xπt ,πt+1 are deterministic functions
of the data-set A, (b) from the chain rule of entropy, (c) follows from (31), (32), and because
conditioning reduces entropy, (d) follows from the storage content at time t given in (30), where
after knowing {Dσ3 , Dσ4 } (or similarly {Dσ2 , Dσ3 , Dσ4 }), the only parts left in Zσt 3 (or Zσt 2 ) are
{Dσ1 (σ3 ), Dσ2 (σ3 )} ({Dσ1 (σ2 )}), (e) follows since out of the cache contents Zjt , the data sub-point
Dk (i) only depends on the sub-point Dk (j), for any i 6= j, (f ) follows from the chain rule of entropy
where Di (W) is the part of Di stored in the excess storage of the workers with the index wj where
j ∈ W at time t, and finally (g) follows from Remark 1.
Summing up over all possible 4! = 24 permutations of the ordered set (1, 2, 3, 4), we arrive at
the following bound,
∗
Rworst-case
d ≥ 3d −

1 X
[H(Dσ1 (σ2 , σ3 , σ4 )) + H(Dσ2 (σ3 , σ4 )) + H(Dσ3 (σ4 ))]
24
σ∈[4!]

1 X
= 3d −
[H(Dσ1 (σ2 , σ3 , σ4 )) + H(Dσ1 (σ2 , σ3 )) + H(Dσ1 (σ2 ))] ,
24

(a)

(35)

σ∈[4!]

where [4!] is the set of all possible permutations of the ordered set (1, 2, 3, 4), and (a) follows due to
the symmetry in the summation by simple change of summation indexes. Following the definition
in (14), we can define Dk,W as the part of Dk stored exclusively in the excess storage of the workers
whose labels are in the set W. According to πt = (1, 2, 3, 4), at time t, Dk,W is only defined for
k 6∈ W (wk does not store Dk as excess storage). Therefore, at time t, we can express the following
entropies in terms of Dk,W as follows:
H(Dk ) =

X

W∈2[1:4]\k

|Dk,W |d,

H(Dk (j)) =

X

W⊆[1:K]\k
j∈W

|Dk,W |d,

(36)

where |Dk,W | is entropy of Dk,W normalized by the data point size d. In the summation term of
(35), we obtain the term |Dk,W | only for |W| ∈ {1, 2, 3}. Next, we show how to find the coefficients
of |Dk,W | for different sizes of W.
• Coefficient of |Dk,W | for |W| = 1: Due to symmetry, we notice that obtaining the coefficient
of |Dk,W | in the summation in (35) for any |W| = 1; is equivalent to obtaining the coefficient of
|D1,{2} |. We get |D1,{2} | in the first term of the summation, i.e., H(Dσ1 (σ2 , σ3 , σ4 )) only if σ1 = 1
which is satisfied in 6 out of the 24 permutations. In the second term, i.e., H(Dσ1 (σ2 , σ3 )), we
obtain |D1,{2} | only if σ1 = 1 and σ4 6= 2 in total number of 4 permutations. In the third term,
i.e., H(Dσ1 (σ2 )), we obtain |D1,{2} | only if σ1 = 1 and σ2 = 2 in total number of 2 permutations.
Therefore, the coefficient of |D1,{2} |, hence any |Dk,W | for |W| = 1, is 6+4+2
= 12 .
24
• Coefficient of |Dk,W | for |W| = 2: Similarly, we obtain the coefficient of |Dk,W | for any
|W| = 2 by obtaining the coefficient of |D1,{2,3} |. We get |D1,{2,3} | in the first two terms of the
summation only if σ1 = 1 which is satisfied in 6 out of the 24 permutations. In the third term, we
obtain |D1,{2,3} | only if σ1 = 1 and σ2 ∈ {2, 3} in total number of 4 permutations. Therefore, the
= 32 .
coefficient of |D1,{2,3} |, hence any |Dk,W | for |W| = 2, is 6+6+4
24
17

• Coefficient of |Dk,W | for |W| = 3: We obtain the coefficient of |Dk,W | for any |W| = 3 by
obtaining the coefficient of |D1,{2,3,4} |. We get |D1,{2,3,4} | in the first three terms of the summation
only if σ1 = 1 which is satisfied in 6 out of the 24 permutations. Therefore, the coefficient of
|D1,{2,3,4} |, hence any |Dk,W | for |W| = 3, is 6+6+6
= 43 .
24
Therefore, we can simplify the bound in (35) as follows:
4

∗
Rworst-case
d ≥ 3d −

1X
2

X

4

k=1 W⊆[1:K]\k
|W|=1

|Dk,W |d −
= 3d −

2X
3

X

i=1 W⊆[1:K]\k
|W|=2

4

|Dk,W |d −

3X
4

X

k=1 W⊆[1:K]\k
|W|=3

x1 d 2x2 d 3x3 d
−
−
,
2
3
4

where x` for ` ∈ [0 : 3] is defined similar to (16) as x` =
both sides by d, we get the following bound:
∗
Rworst-case
≥3−

PK P
k=1

W⊆[1:4]\k: |W|=` |Dk,W |.

|Dk,W |d
(37)

By dividing

x1 2x2 3x3
−
−
.
2
3
4

(38)

Moreover, the data size and the excess storage size constraints for this example follow (15) and
(17), respectively. Hence, we obtain the following constraints:
x0 + x1 + x2 + x3 = 4,

(39)

x1 + 2x2 + 3x3 ≤ 4(S − 1).

(40)

∗
We get the first bound over Rworst-case
by eliminating x1 from (38) using the bound in (40) as
follows:

x1 2x2 3x3
1
2x2 3x3
−
−
≥ 3 − (4(S − 1) − 2x2 − 3x3 ) −
−
2
3
4
2
3
4
x2 3x3 (a)
+
≥ 5 − 2S,
= 5 − 2S +
3
4

∗
Rworst-case
≥3−

(41)

where (a) follows since x2 , x3 ≥ 0.
∗
We get the second bound over Rworst-case
in two steps. First, we eliminate x1 from (38) and
(40) using (39) to get the following two bounds:
1
2x2 3x3
x0 x2 x3
(4 − x0 − x2 − x3 ) −
−
=1+
−
− ,
2
3
4
2
6
4
4(S − 1) ≥ (4 − x0 − x2 − x3 ) + 2x2 + 3x3 = 4 − x0 + x2 + 2x3 .

∗
Rworst-case
≥3−

(42)
(43)

We eliminate x2 from (42) using the bound in (43) to obtain
x0 x2 x3
x0 1
x3
−
−
≥1+
− (4(S − 1) − 4 + x0 − 2x3 ) −
2
6
4
2
6
4
(a)
7 2S x0 x3
7 − 2S
= −
+
+
≥
,
3
3
3
12
3

∗
Rworst-case
≥1+

18

(44)

where (a) follows since x0 , x3 ≥ 0.
∗
Following similar steps, we get a third bound over Rworst-case
by first eliminating x2 from (38)
and (40) using (39) to get the following two bounds:
x1 2
3x3
1 2x0 x1 x3
− (4 − x0 − x1 − x3 ) −
= +
+
− ,
2
3
4
3
3
6
12
4(S − 1) ≥ x1 + 2 (4 − x0 − x1 − x3 ) + 3x3 = 8 − 2x0 − x+ x3 .

∗
Rworst-case
≥3−

(45)
(46)

We eliminate x3 from (45) using the bound in (46) and arrive to
1 2x0 x1 x3
1 2x0 x1
1
+
+
−
≥ +
+
−
(4(S − 1) − 8 + 2x0 + x1 )
3
3
6
12
3
3
6
12
4 S 5x0 x1 (a) 4 − S
+
≥
,
= − +
3
3
6
12
3

∗
Rworst-case
≥

(47)

where (a) follows since x0 , x1 ≥ 0.
∗
In summary, we obtain in (41), (44), and (47) the following bounds on Rworst-case
:
∗
Rworst-case
≥ 5 − 2S,

∗
Rworst-case
≥

7 − 2S
,
3

∗
Rworst-case
≥

4−S
.
3

(48)

The intersection of the three bounds is the lower convex hull of the 4 storage-rate pairs, (S =
∗
m, R = 4−m
m ) for m ∈ [1 : 4], which is the obtained lower bound over Rworst-case given by the blue
curve in Figure 1, satisfying Theorem 2 for K = N = 4.
In our next result, we compare the upper and lower bounds in Theorems 1 and 2, respectively,
and show that they are within a constant multiplication gap of each other.
Theorem 3 For a data-set containing N ∈ N data points, and a set of K ∈ N distributed workers,
∗
the gap ratio between the upper and the lower bounds on Rworst-case
given by Theorems 1, and 2,
respectively, is bounded as follows:
upper
K
Rworst-case
≤
≤ 2.
lower
K −1
Rworst-case

(49)

This Theorem shows that there is a vanishing gap between the bounds as the number of workers

K
K increases, i.e., limK→∞ K−1
= 1. We also show that for the discrete set of storage points
N
considered in Theorem 1, i.e., S = 1 + i K−1
K
K for i ∈ [1 : K], our achievable scheme in fact
optimal, and that the gap only results in the values of storage in between, i.e., memory sharing
∗
is not optimal in this case. For example, consider the bounds on Rworst-case
for K = N = 4
shown in Figure 1. We first notice that the achieved storage-rate pairs (S = 7/4, R = 3/2),
(S = 5/2, R = 2/3), and (S = 13/4, R = 1/4) are optimal. Furthermore, we can show that the
maximum gap between the bounds is at S = 1, which is given by 4/3, satisfying the bound in
(49). The formal proof for the maximum gap analysis for any value of K and N can be found in
Appendix C.

19

The next Theorem provides an improved gap through a new achievable scheme, which we call
as “aligned coded shuffling”.
Theorem 4 For a data-set containing N ∈ N data points, and a set of K ∈ N distributed workers,
∗
the lower bound over Rworst-case
in Theorem 2 is in fact achievable for K < 5 (hence gives the
optimal rate), while for K ≥ 5 is achievable within a gap ratio bounded as
upper
K − 13
Rworst-case
7
≤ .
≤
lower
K −1
6
Rworst-case

(50)

The above theorem is proved by closing the gap between the two bounds in Theorems 1 and 2
N
, and m ∈ {1, K − 2, K − 1}. This can be done with the use of
for the storage values S = m K
sophisticated interference alignment mechanisms, which force the interference seen by each worker
to occupy the minimum possible dimensions. In Appendix D, we present the complete proof of
Theorem 4. To illustrate the new ideas introduced here, we revisit again Example 1 of K = N = 4
∗
to show how the gap between the lower and the upper bounds on Rworst-case
can be closed in this
case.
Example 3 From Figure 1, we notice that if we close the gap for the storage points S = m, for
∗
m ∈ [1 : 3], then we can fully characterize Rworst-case
using memory sharing between the achievable
points (see Claim 1). In the achievability, we consider a different placement strategy, which is also
invariant in the structure. We also consider the aligned coded shuffling scheme for data delivery,
which reduces the rate by forcing the interference to occupy the minimum possible dimensions.
We consider the same subsequent shuffles πt = (1, 2, 3, 4), and πt+1 = (2, 3, 4, 1). Furthermore,
we define δt (i) as the index of the worker being assigned the data point Di at time t. Therefore,
δt = (4, 1, 2, 3), and δt+1 = (1, 2, 3, 4). Next, we discuss the achievability for storage values S = m,
and m ∈ [1 : 3].
• Case m = 1 (S = 1):
As mentioned before in Example 1, the storage placement for the case m = 1 (no excess storage)
is trivial where every worker only stores the data point which needs to be processed. We start by
sending 3 independent linear combinations of the 4 data points as follows:
Xπt ,πt+1 = {L1 (D1 , D2 , D3 , D4 ), L2 (D1 , D2 , D3 , D4 ), L3 (D1 , D2 , D3 , D4 )},

(51)

where L1 , L2 , and L3 are three independent linear functions. We notice that each worker already
stores one data point, and then can decode the 3 remaining data points and acquire the one needed
at time t + 1. For instance, worker w1 has D1 from the previous shuffle at time t, and then can get 3
independent linear functions enough to decode D2 , D3 , and D4 . Therefore, the pair (S = 1, R = 3)
is achievable for K = N = 4 closing the gap in Figure 1 for S = 1. The storage update is also
trivial, where every worker keeps the new assigned data point and discard the remaining three
points.
• Case m = 2 (S = 2):

20

(a)

Cache placement at time t
processing

D1,{2} D1,{3} D1,{4}

At (1)

D2,{1}

D3,{1}

At (2)

D4,{1}

D1,{2}

At (2, 1) At (3, 1) At (4, 1)

D2,{1} D2,{3}
D3,{1}

D4,{1}

At (3)

At+1 (2)

D1,{4}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

Storage at w1

D2,{3}

D3,{4}

At (4)

D4,{3}

D4,{1}
D1,{4}

At (1, 3) At (2, 3) At (4, 3)

D4,{2} D4,{3}
D2,{4}

D3,{4}

At (1, 4) At (2, 4) At (3, 4)

Storage at w3

Storage at w4

excess
storage

Data Delivery and Cache Update at time t + 1

8
< L1 (D3,{4}
L2 (D3,{4}
=
:
L3 (D3,{4}

D2,{4}

D3,{1} D3,{2}
D1,{3}

D4,{2}

Storage at w2

(b)

At+1 (1)

D3,{2}

D2,{4}

At (1, 2) At (3, 2) At (4, 2)

Storage at w1

X⇡t ,⇡t+1

D2,{1} D2,{3}

D4,{2} , D1,{3}
D4,{2} , D1,{3}
D4,{2} , D1,{3}

D3,{1} D3,{2}
D2,{1}

D4,{2}

D3,{4}

D4,{1} , D1,{2}
D4,{1} , D1,{2}
D4,{1} , D1,{2}

At+1 (3)

D1,{2}

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

D2,{3}

D4,{2} D4,{3}
D3,{2}

At+1 (4)

9
D3,{1} ), =
D3,{1} ),
;
D3,{1} )

D3,{4}

D4,{3}

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w3

processing

D1,{2} D1,{3} D1,{4}
D2,{4}

D1,{3}

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

Storage at w2

(c)

D4,{1}

D2,{4} , D2,{3}
D2,{4} , D2,{3}
D2,{4} , D2,{3}

Storage at w4

excess
storage

Relabeling to maintain cache structure
processing

At+1 (1)

D2,{2} D2,{3}
D3,{1}

D4,{1}

D2,{4}

D1,{1}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

Storage at w1

At+1 (2)

D3,{1} D3,{3} D3,{4}
D2,{2}

D4,{2}

At+1 (3)

D1,{2}

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

D4,{1}
D2,{3}

D4,{2} D4,{4}
D3,{3}

D1,{3}

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

Storage at w2

Storage at w3

At+1 (4)

D1,{2} D1,{3}
D2,{4}

D3,{4}

D1,{1}
D4,{4}

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w4

excess
storage

Figure 5: An example on closing the gap of K = 4 workers, N = 4 data points, and m = 2
(S = 2): (a) Structural Invariant Storage placement, (b) Data Delivery and storage update, and
(c) Relabeling some sub-points in red dashed frames to maintain the storage structure. At time t,
every data point Di is partitioned into 3 sub-points each labeled by a unique subset of length 1 of
the set [1 : 4] \ δt (i). At time t + 1, for every data point Di the sub-point Di,{δt+1 (i)} is relabeled as
Di,{δt (i)} . Above the dotted line is the data point fully stored for processing, and below the dotted
line is the excess storage used to store the sub-points containing the worker’s index.

Storage Placement Every data point at time t is partitioned into 3 sub-points of size d/3 bits each,
where every sub-point of the data point Di is labeled by a unique subset W ⊆ [1 : 4] \ δt (i), where
|W| = 1. For example, the data point D1 at time t is partitioned as D1 = {D1,{2} , D1,{3} , D1,{4} }.
The storage placement at time t follows from Figure 5a. First, every worker stores the data point
needed to be processed. Then, in the excess storage, every worker wk stores the sub-points labeled
by the set W, where k ∈ W, e.g., w1 stores the sub-point At (2, 1) = {D2,{1} } from D2 . To
summarize, each worker stores the assigned data point of size d, and for each one of the remaining
3 data points, it stores 1 sub-point of size d/3. That is, the storage requirement is given by
S = 1 + 3 × 1 × 1/3 = 2, which satisfies the storage constraint.
Aligned Coded Shuffling According to the storage placement at time t in Figure 5a, at time t + 1
every worker needs 2 sub-points of the assigned data point, where every needed sub-point is available
at exactly 2 other workers. From an interference perspective, every one of the needed sub-points is
an interference to only one worker, e.g., D3,{4} needed by w2 at time t + 1, is available at w3 and
w4 , and cause interference at w1 (neither needed nor available). Therefore, w1 can face interference
21

from total 2 sub-points: D3,{4} (needed by w2 ), and D4,{2} (needed by w3 ). By aligning these two
sub-points and considering the coded symbol D3,{4} ⊕D4,{2} , we notice the following: 1) This coded
symbol is available at the worker w4 ; 2) It is useful for the two workers w2 , and w3 at the same
time; and 3) It is the only source of interference for w1 . Similarly, we can produce 3 more aligned

symbols to get in total 4 aligned coded symbols, of size d/ 31 bits each, summarized as follows:
D3,{4} ⊕ D4,{2} : Interference at w1 , available at w4 , and useful for w2 , and w3 ;

D1,{3} ⊕ D4,{1} : Interference at w2 , available at w1 , and useful for w3 , and w4 ;
D1,{2} ⊕ D2,{4} : Interference at w3 , available at w2 , and useful for w1 , and w4 ;
D2,{3} ⊕ D3,{1} : Interference at w4 , available at w3 , and useful for w1 , and w2 .

(52)

Therefore, these 4 coded symbols provide every worker with the 2 needed sub-points. Moreover, it
suffices to send only three independent linear combinations of these 4 coded symbols as shown in
Figure 5b, since every worker already has one of them available locally at its storage. The rate of
this transmission is R = 3 × 1/3 = 1, and the pair (S = 2, R = 1) is achievable which closes the
gap in Figure 1 for S = 2.
Storage update and sub-points relabeling The storage update at time t + 1 is done in a way that
preserves the structure of the storage at time t. As shown in Figure 5b, for every data point Di
(processed by the workers wδt (i) , and wδt+1 (i) at epochs t, and t + 1, respectively), the worker wδt (i) ,
which already has Di completely, will only keep the part of Di stored at time t within the excess
storage of the worker wδt+1 (i) , i.e., At+1 (δt+1 (i), δt (i)) = At (δt (i), δt+1 (i)). For example, w1 will
keep the sub-point At+1 (4, 1) = At (1, 4) = {D1,{4} } of D1 in the excess storage at time t + 1.
The relabeling process is shown in Figure 5c for the sub-points in red dashed frames as follows:
for the data point Di , we relabel the sub-points in At+1 (δt+1 (i), δt (i)) = {Di,W }, where δt+1 (i) ∈ W
by replacing δt+1 (i) in W with δt (i). For example, the data point D1 is processed by w1 , and w4 in
the epochs t, and t + 1, respectively. Therefore the following relabeling is done to the sub-points
of D1 :
At+1 (4, 1) = {D1,{4} → D1,{1} }.

(53)

which preserves the structure of the storage.
• Case m = 3 (S = 3):
Storage Placement Every data point at time t is partitioned into 3 sub-points of size d/3 bits each,
where every sub-point of the data point Di is labeled by a unique subset W ⊆ [1 : 4] \ δt (i), where
|W| = 2. For example, the data point D1 at time t is partitioned as D1 = {D1,{2,3} , D1,{2,4} , D1,{3,4} }.
The storage placement at time t follows from Figure 6a. First, every worker stores the data point
needed to be processed. Then, in the excess storage, every worker wk stores the sub-points labeled
by the set W, where k ∈ W, e.g., w1 stores the two sub-points At (2, 1) = {D2,{1,3} , D1,{1,4} } from
D2 . To summarize, each worker stores the assigned data point of size d, and for each one of the
remaining 3 data points, it stores 2 sub-points of size d/3 each. That is, the storage requirement is
given by S = 1 + 3 × 2 × 1/3 = 3, which satisfies the storage constraint.
22

(a)

Cache placement at time t
processing

At (1) D1,{2,3} D1,{2,4} D1,{3,4}

At (2) D2,{1,3} D2,{1,4} D2,{3,4}

D2,{1,3} D3,{1,2} D4,{1,2}
D2,{1,4} D3,{1,4} D4,{1,3}

At (2, 1) At (3, 1) At (4, 1)

Storage at w1

At (3) D3,{1,2} D3,{1,4} D3,{2,4}

At (4) D4,{1,2} D4,{1,3} D4,{2,3}

D1,{2,3} D3,{1,2} D4,{1,2}

D1,{2,3} D2,{1,3} D4,{1,3}

D1,{2,4} D2,{1,4} D3,{1,4}

D1,{2,4} D3,{2,4} D4,{2,3}

D1,{3,4} D2,{3,4} D4,{2,3}

D1,{3,4} D2,{3,4} D3,{2,4}

At (1, 2) At (3, 2) At (4, 2)

At (1, 3) At (2, 3) At (4, 3)

At (1, 4) At (2, 4) At (3, 4)

Storage at w2

(b)

Storage at w3

excess
storage

Storage at w4

Data Delivery and Cache Update at time t + 1

X⇡t ,⇡t+1 =

D2,{3,4}

D3,{1,4}

D4,{1,2}

D1,{2,3}
processing

At+1 (1) D2,{1,3} D2,{1,4} D2,{3,4}

At+1 (2) D3,{1,2} D3,{1,4} D3,{2,4}

At+1 (3) D4,{1,2} D4,{1,3} D4,{2,3}

D3,{1,2} D4,{1,2} D1,{2,4}

D2,{1,3} D4,{1,2} D1,{2,3}

D2,{1,3} D3,{1,2} D1,{2,3}

D2,{1,4} D3,{1,4} D4,{1,3}

D3,{1,4} D4,{1,3} D1,{3,4}

D2,{1,4} D4,{2,3} D1,{2,4}

D2,{3,4} D3,{2,4} D1,{3,4}

D2,{3,4} D3,{2,4} D4,{2,3}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w1

Storage at w2

(c)

At+1 (4) D1,{2,3} D1,{2,4} D1,{3,4}

Storage at w3

excess
storage

Storage at w4

Relabeling to maintain cache structure
processing

At+1 (1) D2,{2,3} D2,{2,4} D2,{3,4}

At+1 (2) D3,{1,3} D3,{1,4} D3,{3,4}

At+1 (3) D4,{1,2} D4,{1,4} D4,{2,4}

D3,{1,3} D4,{1,2} D1,{1,2}

D2,{2,3} D4,{1,2} D1,{2,3}

D2,{2,3} D3,{1,3} D1,{2,3}

D2,{2,4} D3,{1,4} D4,{1,4}

D3,{1,4} D4,{1,4} D1,{1,3}

D2,{2,4} D4,{2,4} D1,{1,2}

D2,{3,4} D3,{3,4} D1,{1,3}

D2,{3,4} D3,{3,4} D4,{2,4}

At+1 (2, 1) At+1 (3, 1) At+1 (4, 1)

At+1 (1, 2) At+1 (3, 2) At+1 (4, 2)

At+1 (1, 3) At+1 (2, 3) At+1 (4, 3)

At+1 (1, 4) At+1 (2, 4) At+1 (3, 4)

Storage at w1

Storage at w2

Storage at w3

At+1 (4) D1,{2,3} D1,{1,2} D1,{1,3}

excess
storage

Storage at w4

Figure 6: An example on closing the gap of K = 4 workers, N = 4 data points, and m = 3
(S = 3): (a) Structural Invariant Storage placement, (b) Data Delivery and storage update, and
(c) Relabeling some sub-points in red dashed frames to maintain the storage structure. At time t,
every data point Di is partitioned into 3 sub-points each labeled by a unique subset of length 2 of
the set [1 : 4] \ δt (i). At time t + 1, for every data point Di the sub-point Di,W where δt+1 (i) ∈ W
is relabeled by replacing δt+1 (i) with δt (i). Above the dotted line is the data point fully stored for
processing, and below the dotted line is the excess storage used to store the sub-points containing
the worker’s index.

Aligned Coded Shuffling According to the storage placement at time t in Figure 6a, at time t + 1
every worker needs only one sub-point of the assigned data point, which is available at the 3 other
workers, e.g., w1 needs D2,{3,4} which is available at the workers w2 , w3 , and w4 . Therefore, we can
send an order 4 symbol useful for the 4 workers at the same time as follows:

Xπt ,πt+1 = D2,{3,4} ⊕ D3,{1,4} ⊕ D4,{1,2} ⊕ D1,{2,3} .

(54)

The rate of this transmission is R = 1 × 1/3 = 1/3, and the pair (S = 3, R = 1/3) is achievable
which closes the gap in Figure 1 for S = 3.
Storage update and sub-points relabeling Similar to the case m = 2, the storage update for the
case m = 3 is shown in Figure 6b. For every data point Di , the worker wδt (i) , which already has Di
completely, will only keep the part of Di stored at time t within the excess storage of the worker
wδt+1 (i) , i.e., At+1 (δt+1 (i), δt (i)) = At (δt (i), δt+1 (i)). For example, w1 will keep the sub-points
23

At+1 (4, 1) = At (1, 4) = {D1,{2,4} , D1,{3,4} } of D1 in the excess storage at time t + 1.
The relabeling process is shown in Figure 6c for the sub-points in red dashed frames in a
similar way to the case m = 2 as follows: for the data point Di , we relabel the sub-points in
At+1 (δt+1 (i), δt (i)) = {Di,W }, where δt+1 (i) ∈ W by replacing δt+1 (i) in W with δt (i). For example,
the data point D1 is processed by w1 , and w4 in the epochs t, and t + 1, respectively. Therefore
the following relabeling is done to the sub-points of D1 :
At+1 (4, 1) = {D1,{2,4} → D1,{1,2} , and D1,{3,4} → D1,{1,3} }.

(55)

which preserves the structure of the storage.
As a conclusion for the example K = N = 4, the lower convex envelope of the achievable pairs
(S = m, R = 4−m
m ), for m ∈ [1 : 4], is the optimal storage-rate trade-off.

4

Conclusion

We considered the worst-case trade-off between the amount of storage and communication overhead
for the data shuffling problem. First, we presented an information theoretic formulation of the
problem. Following that, we proposed a novel uncoded-structural invariant storage placement and
update strategy for different storage values at the workers. This placement strategy allowed for
applying a similar coding scheme to the one in [40]. Through a novel bounding methodology similar
to [38, 39], we derived an information theoretic lower bound on the worst-case communication rate
as a function of the storage, which showed that the resulting communication overhead of our scheme
K
, where K is the number of workers. Furthermore,
is within a maximum multiplicative factor of K−1
we presented a new scheme inspired by the idea of interference alignment, which closes the gap
and hence achieves the optimal worst-case rate-storage trade-off for K < 5, and further reduces the
K− 1
maximum multiplicative factor to K−13 for K ≥ 5.

References
[1] L. Bottou. Stochastic gradient descent tricks. Neural Networks: Tricks of the Trade, pages
421–436, 2012.
[2] O. Shamir. Without-replacement sampling for stochastic gradient methods: Convergence
results and application to distributed optimization. CoRR, abs/1603.00570v2, 2016.
[3] M. Gürbüzbalaban, A. Ozdaglar, and P. Parrilo. Why random reshuffling beats stochastic
gradient descent. CoRR, abs/1510.08560, 2015.
[4] S. Shi, G. Hsu, K. Nahrstedt, and R. Campbell. Using graphics rendering contexts to enhance the real-time video coding for mobile cloud gaming. In Proceedings of the 19th ACM
international conference on Multimedia, pages 103–112. ACM, 2011.

24

[5] J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008.
[6] J. Dean and L. A. Barroso. The Tail at Scale. Communications of the ACM, 56(2):74–80,
2013.
[7] G. Ananthanarayanan, S. Kandula, A. G. Greenberg, I. Stoica, Y. Lu, B. Saha, and E. Harris.
Reining in the Outliers in Map-Reduce Clusters using Mantri. In Proceedings of USENIX
OSDI, 2010.
[8] G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. Effective Straggler Mitigation:
Attack of the Clones. In Proceedings of USENIX NSDI, 2013.
[9] N. B. Shah, K. Lee, and K. Ramchandran. When do Redundant Requests Reduce Latency?
In Proceedings of the 51st Annual Allerton conference, 2013.
[10] N. B. Shah, K. Lee, and K. Ramchandran. When do redundant requests reduce latency? IEEE
Transactions on Communications, 64(2):715–722, 2016.
[11] D. Wang, G. Joshi, and G. W. Wornell. Efficient Task Replication for Fast Response Times
in Parallel Computation. In Proceedings of ACM SIGMETRICS, 2014.
[12] R. Blumofe and C. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM), 46(5):720–748, 1999.
[13] M. Attia and R. Tandon. Combating computational heterogeneity in large-scale distributed
computing via work exchange. arXiv preprint arXiv:1711.08452, 2017.
[14] K. Shvachko, H. Kuang, S. Radia, and R. Chansler. The Hadoop Distributed File System.
In Proceedings of IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST),
pages 1–10, May 2010.
[15] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: Cluster Computing with Working Sets. In Proceedings of USENIX HotCloud, 2010.
[16] D. Datla, X. Chen, T. Tsou, Sahana S. Raghunandan, S. Hasan, J. Reed, C. Dietrich, T. Bose,
B. Fette, and J. Kim. Wireless distributed computing: a survey of research challenges. IEEE
Communications Magazine, 50(1), 2012.
[17] U. Drolia, R. Martins, J. Tan, A. Chheda, M. Sanghavi, R. Gandhi, and P. Narasimhan.
The case for mobile edge-clouds. In Ubiquitous Intelligence and Computing, 2013 IEEE 10th
International Conference on and 10th International Conference on Autonomic and Trusted
Computing (UIC/ATC), pages 209–215. IEEE, 2013.
[18] L. Song, S. Srinivasavaradhan, and C. Fragouli. The benefit of being flexible in distributed
computation. arXiv preprint arXiv:1705.08464, 2017.

25

[19] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran. Speeding up distributed machine learning using codes. IEEE Transactions on Information Theory, 2017.
[20] R. Tandon, Q. Lei, A. Dimakis, and N. Karampatziakis. Gradient coding. arXiv preprint
arXiv:1612.03301, 2016.
[21] Kangwook Lee, Changho Suh, and Kannan Ramchandran. High-dimensional coded matrix
multiplication. In Information Theory (ISIT), 2017 IEEE International Symposium on, pages
2418–2422. IEEE, 2017.
[22] S. Dutta, V. Cadambe, and P. Grover. Coded convolution for parallel and distributed computing within a deadline. arXiv preprint arXiv:1705.03875, 2017.
[23] W. Halbawi, N. Azizan-Ruhi, F. Salehi, and B. Hassibi. Improving distributed gradient descent
using Reed-Solomon codes. arXiv preprint arXiv:1706.05436, 2017.
[24] Q. Yu, M. Maddah-Ali, and A. Avestimehr. Polynomial codes: an optimal design for highdimensional coded matrix multiplication. arXiv preprint arXiv:1705.10464, 2017.
[25] A. Reisizadeh and R. Pedarsani. Latency analysis of coded computation schemes over wireless
networks. arXiv preprint arXiv:1707.00040, 2017.
[26] S. Li, M. A. Maddah-Ali, and S. Avestimehr. Coded MapReduce. In Proceedings of the 53rd
Annual Allerton conference, September 2015.
[27] S. Li, M. Maddah-Ali, Q. Yu, and A. Avestimehr. A fundamental tradeoff between computation
and communication in distributed computing. arXiv preprint arXiv:1604.07086, 2016.
[28] Q. Yu, S. Li, M. Maddah-Ali, and A. Avestimehr. How to optimally allocate resources for
coded distributed computing? arXiv preprint arXiv:1702.07297, 2017.
[29] Y. Ezzeldin, M. Karmoose, and C. Fragouli. Communication vs distributed computation: an
alternative trade-off curve. arXiv preprint arXiv:1705.08966, 2017.
[30] S. Li, M. Maddah-Ali, and A. Avestimehr. Coded distributed computing: Straggling servers
and multistage dataflows. In Proceedings of the 54th Annual Allerton conference, September
2016.
[31] S. Li, M. Maddah-Ali, and A. Avestimehr. A unified coding framework for distributed computing with straggling servers. In Proceedings of the IEEE Globecom, pages 1–6. IEEE, 2016.
[32] M. Attia and R. Tandon. Information theoretic limits of data shuffling for distributed learning.
In Global Communications Conference (GLOBECOM), pages 1–6. IEEE, 2016.
[33] M. Attia and R. Tandon. On the worst-case communication overhead for distributed data
shuffling. In Proceedings of the 55th Annual Allerton conference, September 2016.

26

[34] S. Li, Q. Yu, M. Maddah-Ali, and A. Avestimehr. Edge-facilitated wireless distributed computing. In Global Communications Conference (GLOBECOM), pages 1–7. IEEE, 2016.
[35] S. Li, Q. Yu, M. Maddah-Ali, and A. Avestimehr. A scalable framework for wireless distributed
computing. IEEE/ACM Transactions on Networking, 25(5):2643 – 2654, 2017.
[36] Z. Bar-Yossef, Y. Birk, T. Jayram, and T. Kol. Index coding with side information. IEEE
Transactions on Information Theory, 57(3):1479–1494, 2011.
[37] L. Song and C. Fragouli. A pliable index coding approach to data shuffling. arXiv preprint
arXiv:1701.05540, 2017.
[38] K. Wan, D. Tuninetti, and P. Piantanida. On the optimality of uncoded cache placement. In
Information Theory Workshop (ITW), 2016 IEEE, pages 161–165. IEEE, Sept 2016.
[39] Q. Yu, M. Maddah-Ali, and A. Avestimehr. The exact rate-memory tradeoff for caching with
uncoded prefetching. In Information Theory (ISIT), 2017 IEEE International Symposium on,
pages 1613–1617. IEEE, 2017.
[40] M. A. Maddah-Ali and U. Niesen. Fundamental limits of caching. 60(5):2856–2867, February
2015.

Appendix A

∗
(Proof of Theorem 1)
Upper Bound on Rworst-case

Following Example 1, we present our general achievability for any
number of data points N , and any storage value S. Our scheme has
invariant storage placement/update phase; and data delivery phase.
upper
upper bound on the optimal worst-case rate, i.e., Rworst-case
stated in

A.1

number of workers K, any
two main phases: structural
This scheme also proves the
Theorem 1.

Structural Invariant Placement

We first propose a structural invariant placement, which allows applying a similar data delivery
scheme to the one proposed in [40]. The placement procedure involves updating the storage content
for each worker after each shuffle in order to maintain the structure of the storage. Since the shuffling
process at each time is done randomly, all the data points not being processed by a worker wk are
of equal importance to reduce the communication overhead in the next shuffle. Consequently, the

N
d is equally divided among these points, where we assume
amount of excess storage of size S − K
uncoded storage placement.
N
We focus on a discrete set of storage values given by S = 1 + i( K−1
K ) K , for i ∈ [0 : K]. The
values in between can then be achieved by memory sharing as stated in Claim 1. At time t, the
worker wk first stores the batch assigned for processing, At (k), in order to satisfy the processing
N
d bits of the available storage. That is if a data point D ∈ At (k),
constraint in (6), which requires K
N
N
then D is fully stored in Zkt . The excess storage of size (S − K
)d = i( K−1
K )( K )d is used as follows:

every data point D ∈ A is divided across the dimension d into Ki non-overlapping parts of size
27


d/ Ki bits each, and then each part is labeled by a unique set W ⊆ [1 : K] of size i. The worker
wk stores the sub-point DW in the excess storage, where D 6∈ At (k), only if k ∈ W. Therefore, the

number of sub-points a worker wk is storing from a point D 6∈ At (k); is given by K−1
i−1 sub-points.
N
The total number of these points is N − K
= (K−1)N
points. Then, the total size necessary for
K
excess storage is




N
K −1
d
i(K − 1)N
(K − 1)N
d= S−
d,
×
× K =
2
K
K
K
i−1
i

(56)

which satisfies the memory constraint.

A.2

Data Delivery Phase

Next, we present our proposed delivery scheme to satisfy the new data assignment characterized
by the shuffles (πt , πt+1 ). According to the adopted placement strategy, whenever a new data point


is newly assigned to a worker, it already has K−1
out of the total Ki partitions. Therefore,
i−1



K−1
.
the number of sub-points still needed for every new assigned data point is Ki − K−1
i
i−1 =
Moreover, for the worst-case scenario, each worker is assigned completely new data points, and
N
there are K
new data points for each worker, i.e., At (k) ∩ At+1 (k) = φ. This gives the total number
N
of data sub-points needed by each worker in the worst case to be K−1
i
K.
According to the placement strategy, every data sub-point DW , is stored at least in i different
workers. Now, if we pick any set M ⊆ [1 : K] of the workers, where |M| = i + 1, then for
each worker wk , where k ∈ M, and for each point D newly assigned to wk in the next shuffle,
i.e., D 6∈ At (k), and D ∈ At+1 (k), there is at least one sub-point needed by k from the remaining
N
order i + 1 coded symbols in the
workers in the set, labeled as DM\k . Therefore, we can send K

K
t+1
form ⊕ AM\k (k), of size d/ i each, useful for all the i + 1 workers in M in the same time.
k∈M

K
number of times,
Considering all the possible sets M of size i + 1, this process is repeated i+1

K N
which gives i+1 K coded symbols given by
Xπt ,πt+1 =









∪
⊕ At+1
M\k (k) .

M⊆[1:K]
k∈M


|M|=i+1

(57)

The corresponding total worst-case number of bits sent over the shared link is given by
Rworst-case d =




K
N
d
N (K − i)
×
× K =
d.
i+1
K
K(i + 1)
i

(58)

It is important to notice that the total number of times wk becomes a member of the set M is

N
K−1
. Therefore, by sending the coded symbols in (57), every worker gets K−1
i
i
K sub-points in
N
total, which are enough to recover K data points in the worst-case scenario as previously discussed.
Using the memory sharing concept in Claim 1, we can achieve the lower convex envelope of the

28

following K + 1 points:




K −1 N
N (K − i)
upper
S = 1+i
,
, Rworst-case =
K
K
K(i + 1)

∀i ∈ [0 : K],

(59)

which completes the proof of Theorem 1.

A.3

Storage Update Procedure

In order to maintain the structure of the storage after the next shuffle at time t + 1, the storage
update procedure takes place at worker wk for every point D ∈ A according to the following cases:
• D ∈ At (k), and D ∈ At+1 (k): In this case D remains stored completely in Zkt+1 .
t+1
• D 6∈ Atk , and D ∈ At+1
k : After the data delivery, worker wk stores D completely in Zk .
• D ∈ At (k), and D 6∈ At+1 (k): Out of the point D previously stored completely in Zkt , worker wk
chooses to stores in Zkt+1 the sub-points DW where k ∈ W.
• D 6∈ At (k), and D 6∈ At+1 (k): Nothing changes about the storage of D in the excess storage of
Zkt+1 , and wk keeps the same sub-points of D previously stored in Zkt , i.e., DW where k ∈ W.

Appendix B

∗
Lower Bound on Rworst-case
(Proof of Theorem 2)

In this section, we present an information theoretic lower bound on the worst-case communication
rate. Following Remark 1, we start by considering the following shuffle (πt , πt+1 ) at time t + 1: for a
permutation of the worker indexes σ : (1, 2, . . . , K) → (σ1 , σ2 , . . . , σK ), the worker wσk at time t + 1
is assigned the data batch that was assigned to the worker wσk−1 at time t, i.e., At+1 (σk ) = At (σk−1 ),
which also gives the following condition using (10):
H(At+1 (σk )|Zσt k , Xπt ,πt+1 ) = H(At (σk−1 )|Zσt k , Xπt ,πt+1 ) = 0.

(60)

Next, we prove that H(A|Ztσ[2:K] , Xπt ,πt+1 ) = 0 using (6), and (60) as follows:
H(A|Ztσ[2:K] , Xπt ,πt+1 )

t

= H(A ([1 :

≤

K
X

K])|Ztσ[2:K] , Xπt ,πt+1 )

≤

K
X

H(At (σj )|Ztσ[2:K] , Xπt ,πt+1 )

j=1

H(At (σj )|Zσt j ) + H(At (σ1 )|Zσt 2 , Xπt ,πt+1 ) = 0.

j=2

29

(61)

Using (60), and (61), we obtain the following bound:




N d = H(A) = I A; Ztσ[2:K] , Xπt ,πt+1 + H A|Ztσ[2:K] , Xπt ,πt+1




(a)
≤ H Ztσ[2:K] , Xπt ,πt+1 − H Ztσ[2:K] , Xπt ,πt+1 |A



(b)
= H Xπt ,πt+1 , Zσt K + H Ztσ[2:K−1] ] |Xπt ,πt+1 , Zσt K


≤ H Xπt ,πt+1 + H

Zσt K



+

K−1
X
i=2


≤ Rπ∗ t ,πt+1 d + H At (σK ) + H At (σ[1:K−1] , σK )

(c)

+

K−1
X
i=2





H Zσt i |Ztσ[i+1:K] , Xπt ,πt+1



H Zσt i |Ztσ[i+1:K] , Xπt ,πt+1 , At (σ[i:K] )


N
d + H At (σ[1:K−1] , σK )
K
K−1

X 
+
H At (σ[1:i−1] , σi )|Ztσ[i+1:K] , Xπt ,πt+1 , At (σ[i:K] )

(d)

= Rπ∗ t ,πt+1 d +

i=2

(e)

≤ Rπ∗ t ,πt+1 d +

= Rπ∗ t ,πt+1 d +
(f )

=

Rπ∗ t ,πt+1 d


X 
 K−1
N
d + H At (σ[1:K−1] , σK ) +
H At (σ[1:i−1] , σi )|Ztσ[i+1:K]
K
i=2

N
d+
K

K X
i−1
X
i=2 j=1



H At (σj , σi )|Zt[σi+1 :σK ]



K X
i−1
X

N
+ d+
H At (σj , σi )|At (σj , σ[i+1:K] )
K
i=2 j=1

=
(g)

=

Rπ∗ t ,πt+1 d
Rπ∗ t ,πt+1 d

N
+ d+
K

K−1
X

K
X

j=1 i=j+1


H At (σj , σi )|At (σj , σ[i+1:K] )

K−1
X

N
H At (σj , σ[j+1:K] ) ,
+ d+
K

(62)

j=1

where (a) follows from (61), (b) follows from (4), and (8), where Ztσ[2:K] , and Xπt ,πt+1 are deterministic functions of the data-set A, (c) follows from (6), (60), and the constraint on storage in (13), (d)
also follows from (13) where after knowing At (σ[i:K] ), the only parts left in Zσt i are At (σ[1:i−1] , σi ),
(e) because conditioning reduces entropy, (f ) follows since At (σj , σi ) only depends on the parts of
the batch At (σj ) stored at Zt[σi+1 :σK ] , and finally (g) follows from the chain rule of entropy. From
the definition in (14), we can write At (σj , σ[j+1:K] ) as
At (σj , σ[j+1:K] ) =

∪

∪

S⊆σ[j+1:K] : S6=φ W⊆[1:K]\σj : S∈W

30

AtW (σj )

(63)


Therefore, we can upper bound the entropy H At (σj , σ[j+1:K] ) as

H At (σj , σ[j+1:K] ) ≤

X

X

S⊆σ[j+1:K] : S6=φ W⊆[1:K]\σj : S∈W

=

X

W⊆[1:K]\σj

|AtW (σj )| d −

|AtW (σj )| d

X

W⊆σ[1:j−1]

|AtW (σj )| d,

(64)

where |AtW (j)| is the size of the sub-batch AtW (j) normalized by d. Therefore, by applying (64) in
∗
(62), we get a bound over Rπ∗ t ,πt+1 , which is also a lower bound over Rworst-case
following Remark 1,
as follows:


K−1
X
X
X
N
∗

−
Rworst-case
≥ Rπt ,πt+1 ≥ N −
|AtW (σj )| −
|AtW (σj )|
K
j=1
W⊆σ[1:j−1]
W⊆[1:K]\σj


K−1
X K−1
X
N
−
=N−
K
`=0 j=1






X

W⊆[1:K]\σj
|W|=`

|AtW (σj )|

−

X

W⊆σ[1:j−1]
|W|=`




|AtW (σj )| .


(65)

For K! possible permutations σ of the ordered set (1, 2, . . . , K), we get K! different bounds over
from (65). Summing up over all the possible K! permutations σ, we get

∗
Rworst-case

∗
Rworst-case
≥N−



K−1 K−1
1 X X X 
N

−

K
K!

`=0 j=1 σ∈[K!]

X

W⊆[1:K]\σj
|W|=`

|AtW (σj )| −

X



W⊆σ[1:j−1]
|W|=`



|AtW (σj )| ,


(66)

where [K!] is defined as the set of all possible permutations of the ordered set (1, 2, . . . , K), which
contains K! permutations. Due to symmetry, for each value of a (`, j) pair in the outer summation
in (66), where ` ∈ [0 : K − 1] and j ∈ [1 : K − 1], the coefficients of each |AtW (k)| in the inner
summation for k ∈ [1 : K] and |W| = ` are equal. Therefore, we can write the inner summation in
(66) in the following form:


X 




σ∈[K!]

X

W⊆[1:K]\σj
|W|=`

|AtW (σj )| −

X

W⊆σ[1:j−1]
|W|=`



K
 
X

j,`
|AtW (σj )| = cj,`
−
c
1
2


X

k=1 W⊆[1:K]: |W|=`



j,`
= cj,`
−
c
x` ,
1
2

|AtW (k)|
(67)

j,`
where cj,`
1 , and c2 are the two coefficients of x` coming from the two inner summations in the LHS
j,`
of (67). From (67), finding cj,`
1 , and c2 is the same as finding the coefficients of one realization of
k, and W on the right side of the equation, and we consider for instance At[2:`+1] (1). In the first

31

sum, we get cj,`
1 by counting the number of permutations where σj = 1, which is given by
cj,`
1 = (K − 1)!.

(68)

In the second sum, we get cj,`
2 by counting the number of permutations such that σj = 1, and
σj+1 , . . . , σK ∈ [` + 2 : K], which is given by
cj,`
2

(K − ` − 1)!
=
(j − 1)! =
(j − ` − 1)!



j−1
`
 (K
K−1
`

− 1)!.

(69)

Therefore, we can write the summation in (67) in the following form:


X 




σ∈[K!]

X

W⊆[1:K]\σj
|W|=`

|AtW (σj )| −



X

W⊆σ[1:j−1]
|W|=`



|AtW (σj )| =


(K − 1)! −



j−1
`
 (K
K−1
`

!

− 1)! x` .

(70)

Now, we use (70) in (66) to obtain the following bound:
∗
Rworst-case

#
"

K−1 K−1
j−1
1 X X
N
`
−
(K − 1)! − K−1 (K − 1)! x`
≥N−
K
K!
`
`=0 j=1
#
"

K−1
K−1
N
1 X
`+1
=N−
−
(K − 1)(K − 1)! − K−1 (K − 1)! x`
K
K!
`
`=0


K−1
N
1 X
K −`−1
=N−
−
(K − 1) −
x`
K
K
t+1
(a)

=

K−1
X
`=0

`=0
K−1
X

N
x` −
−
K

`=0

K−1
X 1
`
N
x` =
x` − ,
`+1
`+1
K

(71)

`=0

where (a) follows from the data size constraint in (15). Next, we obtain K − 1 different lower
∗ , by eliminating the pairs (x
bounds on the optimal worst-case transmission rate Rwc
j−1 , xj ), for
each j ∈ [1 : K − 1], in the equation (71) using the equations (15) and (17). We use (15) to write
xj−1 as follows:
xj−1 = N −

X

x` .

(72)

`∈[0:K]\j−1

We first apply (72) in (71) to obtain
∗
Rworst-case
≥

=

X

`∈[0:K−1]\j−1

N (K − j)
−
Kj



1
1
x` + N −
`+1
j
X

`∈[0:K−1]\j−1

32

X

`∈[0:K−1]\j−1

`−j+1
x` .
j(` + 1)



x`  −

N
K
(73)

We next apply (72) in the excess storage constraint of (17) to obtain
X

`∈[0:K−1]\j−1

X

`∈[0:K−1]\j−1



`x` + (j − 1) N −

X

`∈[0:K]\j−1



N
(` − j + 1) x` ≤ K S − j
K







N

x` ≤ K S −
,
K
.

(74)

Now, we need to eliminate xj from (73). We use (74) to bound xj as


N
xj ≤ K S − j
−
K

X

`∈[0:K−1]\{j−1,j}

(` − j + 1) x` .

(75)

Then, we use this bound in (73) as follows:
∗
Rworst-case

≥

N (K − j)
−
Kj

=

1
`−j+1
x` −
xj
j(` + 1)
j(j + 1)

`∈[0:K−1]\{j−1,j}

N (K − j)
≥
−
Kj

(a)

X

X

`∈[0:K−1]\{j−1,j}
N
jK

N (K − j) K S −
−
Kj
j(j + 1)



+


N
N (K − j) K S − j K
≥
−
,
Kj
j(j + 1)


N
K S − jK
`−j+1
x` −
+
j(` + 1)
j(j + 1)
X

X

`∈[0:K−1]\{j−1,j}

(` − j + 1)
x`
j(j + 1)

λ` x`

`∈[0:K−1]\{j−1,j}

(b)

(76)

where (a) follows from (75) where the coefficient of xj in the above equation is negative for all
j ∈ [1 : K − 1], and (b) since the coefficients, λ` , of x` > 0 are positive for ` ∈ [0 : K − 1] \ {j − 1, j},
which can be shown in the following:
λ` =

(` − j)(` − j + 1)
`−j+1 `−j+1
−
=
,
j(j + 1)
j(` + 1)
j(j + 1)(` + 1)

(77)

where j, j + 1, ` + 1 > 0 for `, j ≥ 0, then we only need to show that (` − j)(` − j + 1) > 0 for
` ∈ [0 : K − 1] \ {j − 1, j}. This can be easily checked by assuming y = ` − j, then y(y + 1) is only
negative in the range −1 < y < 0, or j − 1 < ` < j, which is not in the range of ` in the above
summation.
The lower bound in (76) is a linear function
of S for a fixed value of j ∈ [1 : K − 1] passing

N (K−j)
(K−j−1)
N
N
, and S2 = (j + 1) K
. We obtain
, R2 = N K(j+1)
through the points S1 = j K , R1 = Kj
K − 1 such lower bounds for every j ∈ [1 : K − 1], which eventually give the lower bound over
∗
Rworst-case
as the lower convex envelope of the following K points:


N
N (K − m)
lower
S = m , Rworst-case
=
,
K
Km
33

∀m ∈ [1 : K],

(78)

which completes the proof of Theorem 2.

Appendix C

Maximum Gap Analysis (Proof of Theorem 3)

∗
To characterize the maximum gap between the obtained bounds over Rworst-case
, we first express

N
N
the storage S as multiples of K , i.e., S = m K , for 1 ≤ m ≤ K. From Theorem 1 for 1 + i K−1
≤
K

K−1
m ≤ 1 + (i + 1) K , and i ∈ [0 : K − 1], we can achieve the line joining the two points m =


(K−i) 
(K−i−1) 
1 + i K−1
, R = NK(i+1)
, and m = 1 + (i + 1) K−1
, R = N K(i+2)
, which gives the following
K
K
∗
upper bounds over Rworst-case as
N (K−i)
K(i+1)

i K−1
K

upper
Rworst-case
−

N (K−i−1)
N (K−i)
K(i+2) − K(i+1)


(i + 1) K−1
− 1 + i K−1
K
K

N (K + 1)
,
(K − 1)(i + 1)(i + 2)
1+
m− 1+


K −1
N (K + 1)
N (K − i)
upper
m−1−i
,
−
Rworst-case =
K(i + 1)
(K − 1)(i + 1)(i + 2)
K
=

=−

(79)



for 1 + i K−1
≤ m ≤ 1 + (i + 1) K−1
, and i ∈ [0 : K − 1]. Also, from (76) we have the lower
K
K
∗
bounds over Rworst-case as
lower
Rworst-case
=

N (K − j) N (m − j)
−
,
Kj
j(j + 1)

(80)

for j ≤ m ≤ j + 1, and j ∈ [1 : K − 1].
Due to the properties of the piece-wise linear functions, we obtain the maximum gap at one of
the following 2K − 1 values of m: m = j , for j ∈ [1 : K − 1], or m = 1 + i K−1
K , for i ∈ [1 : K].

C.1

, and i ∈ [1 : K]
Gap Analysis for m = 1 + i K−1
K

lower
at
We first notice that when i ∈ [1 : K], then i ≤ m ≤ i + 1. Therefore, the lower bound Rworst-case
K−1
m = 1 + i K follows from (80) where j = i:

lower
Rworst-case




N (K − i) N 1 + i K−1
K −1
K −i
=
−
m=1+i
K
Ki
i(i + 1)
N (K − i) N (K − i)
N (K − i)
=
−
=
,
Ki
Ki(i + 1)
K(i + 1)

(81)

which matches the upper bound in (79), when m = 1 + i K−1
K . Therefore, the proposed achievable
K−1
scheme is optimal for m = 1 + i K , where i ∈ [1 : K].

34

C.2

Gap Analysis for m = j, and j ∈ [1 : K − 1]



We first notice that when m = j, then 1 + (j − 1) K−1
≤ m ≤ 1 + j K−1
for j ∈ [1 : K − 1].
K
K
upper
Therefore, the upper bound Rworst-case at m = j follows from (79) where i = j − 1:
upper
Rworst-case
(m



N (K − j + 1)
K −1
N (K + 1)
= j) =
j − 1 − (j − 1)
−
Kj
j(K − 1)(j + 1)
K
N (K − j + 1)
N (K + 1)(j − 1)
=
−
Kj
jK(K − 1)(j + 1)


(K + 1)(j − 1)
N (K − j)
N
1−
,
=
+
Kj
Kj
(K − 1)(j + 1)

(82)

∗
whereas the lower bound on Rworst-case
(m = j) follows from (80) directly as follows:
lower
Rworst-case
(m = j) =

N (K − j)
.
Kj

(83)

Hence, the ratio between the bounds follows by dividing (82) by (83) as
upper
1
Rworst-case
=1+
lower
K −j
Rworst-case



(K + 1)(j − 1)
2
1−
=1+
,
(K − 1)(j + 1)
(K − 1)(j + 1)

j ∈ [1 : K − 1].

(84)

We notice that ratio in (84) is a decreasing function in j. Therefore, we obtain the maximum gap
N
with the smallest value of j, i.e., j = 1, which is the no excess storage case S = K
. Applying j = 1
in (84), we obtain the maximum gap ratio as follows:
upper
Rworst-case
1
K
=1+
=
,
lower
(K − 1)
K −1
Rworst-case

(85)

which completes the proof of Theorem 3.

Appendix D

Closing the Gap (Proof of Theorem 4)

Based on Example 3, we introduce the general achievability to close the gap for some storage values.
N
, for m ∈ {1, K − 2, K − 1}, any number
In particular, we consider the storage values S = m K
of workers K, and any number of data points N . We also consider a variation of the structural

invariant storage placement. Every data point Di for i ∈ [1 : N ] is now partitioned into K−1
m−1
non-overlapped sub-points. As suggested in the Example 3, the labeling for the data sub-points is
changing over time as follows: At the time epoch t, the data sub-points of the data point Di are
labeled by unique subsets Wt ⊆ [1 : K] \ δt (i), where δt (i) is the index of the worker assigned to the
data point Di at time t. Every worker stores the assigned data points as well as the data sub-points
having the worker’s index in their labels. Therefore, any partition of a data point is stored at total
number of m workers; m − 1 workers are storing it as excess storage, and 1 worker is assigned the
whole corresponding data point for processing.
For invariant structure placement, the change in the labels at time t + 1 is required only for

35

the data sub-points Di,Wt , where δt+1 (i) ∈ Wt , by replacing δt+1 (i) with δt (i) in the label Wt to
obtain the newly labeled sub-points Di,Wt+1 where δt (i) ∈ Wt+1 . Therefore, these newly labeled
sub-points are required now to be stored in the excess storage of the worker wδt (i) , which already
has the data point Di fully available at its cache at time t. Then, there is no need to deliver these
sub-points, and the storage structure can be preserved.
The number of data sub-points of the point Di needed to be stored at worker wk at time t,


K−1
N
where δt (i) 6= k (Di 6∈ At (k)) is K−2
m−2 of size d/ m−1 bits each. In total, we have (K − 1) K such
data points where δt (i) 6= k for the worker wk . Therefore, the worker wk needs to store in the
excess storage data of total size


K −2
N
×
(K − 1) ×
K
m−2

N
 = (m − 1) d =
K−1
K
m−1
d



N
S−
K



d,

(86)

which satisfies the memory constraint.
Before we proceed to the delivery mechanism we define At,t+1 (i; j) = At (i) ∩ At+1 (j) as the
part of data assigned to wj at time t + 1 which was also assigned to wi at time t. Furthermore, we
t,t+1
define Si,j
= |At,t+1 (i; j)| as the number of such data points. Therefore, the data batches At (i)
and At+1 (i) can then be written as
t,t+1
At (i) = ∪K
(i; j),
j=1 A

t,t+1
At+1 (i) = ∪K
(j; i).
j=1 A

Since we have the size of the data batches is fixed as |At (i)| = |At+1 (i)| =
following property:
K
X

t,t+1
Si,j

j=1

=

K
X

t,t+1
Sj,i
=

j=1

N
.
K

(87)
N
K,

we obtain the

(88)

Remark 2 (Data-flow Conservation Property) We next state an important property satisfied by any shuffle, namely the data-flow conservation property:
X

t,t+1
Si,j
=

j∈[1:K]\i

X

t,t+1
Sj,i
.

(89)

j∈[1:K]\i

t,t+1
The proof of this property follows directly by subtracting Si,i
from the two sides of (88), and
has the following interesting interpretation: the total number of new data points that need to be
delivered to worker wi (and are present elsewhere), i.e., the RHS of (89), is exactly equal to the
total number of data points that worker wi has that are desired by the other workers, which is the
LHS of (89).
t,t+1
The rate Rπt ,πt+1 is characterized by Si,j
for i, j ∈ [1 : K]. These shuffling parameters can
t,t+1
t,t+1
be held in the matrix S
= [Si,j ]i,j , which can be named as the shuffling matrix. Moreover,
according to the property in (88) the shuffling matrix S t,t+1 is a K × K square matrix with the row
N
. In the following discussion, we drop the superscript t, t + 1
sum equals the column sum equals K

36

t,t+1
from At,t+1 (i; j), and Si,j
for short notation.

Lemma 1 The rate achieved when the diagonal entries of the shuffling matrix are greater than
zero, i.e., when Si,i > 0 for i ∈ [1 : K], is no larger than the worst-case rate.
Proof: The proof is straight forward, where Si,i is the number of data points that are needed by
worker wi at times t and t + 1. Therefore, they remain in the storage of the worker wi and do not
participate in the communication process. If Si,i > 0, then less number of data points are needed
by worker wi and the rate is no larger than the worst-case rate, which completes the proof of the
lemma. 
Corollary 5 For the worst-case rate analysis, we can assume that every worker is assigned only
new data points, i.e., Si,i = 0. Hence, the data conservation property in (89) can be written as
X

Si,j =

j∈[1:K]\j

D.1

X

Sj,i =

j∈[1:K]\j

N
.
K

(90)

Closing the Gap for m = 1

N
We consider the storage value m = 1 (S = K
), which is the no-excess storage case considered in our
N
, Rworst-case =
previous work [33] for any arbitrary shuffle. One can easily show that the pair (S = K
N
(K − 1) K ) is achievable by sending K − 1 linear independent combinations of the K data batches at
time t, i.e., At (1), . . . , At (K), to satisfy any data assignment at time t + 1. Since every worker wk
has already the data batch At (k) already stored in its cache, it can solve for the remaining K − 1
batches and obtain the whole data-set to store the new data assignment.

D.2

Closing the Gap for m = K − 1

According to the adopted placement strategy, whenever a new data point is needed at any worker,


K−1
it already has K−2
m−2 out of the total m−1 partitions, that is for the storage value m = K − 1
N
), only 1 out of K − 1 sub-points is needed. Furthermore, this needed data sub-point
(S = (K − 1) K
is already available at the remaining m = K −1 workers. Therefore, for the Si,j data points assigned
to worker wj and available at wi , i.e., A(i; j), the data sub-batch A[1:K]\{i,j} (i; j) is the only part
needed to be transmitted to wj , which is available at all the workers except wj . For the worst-case
scenario according to Corollary 5, we assume every worker is assigned completely new data batch,
i.e., Si,i = 0 for all i ∈ [1 : K]. Therefore, we can write the total part needed to be transmitted to
d
N
data sub-points each of size K−1
each, and the
wj as ∪i∈[1:K]\j A[1:K]\{i,j} (i; j), which consists of K
size of ∪i∈[1:K]\j A[1:K]\{i,j} (i; j) (normalized by d) is
| ∪i∈[1:K]\j A[1:K]\{i,j} (i; j)| =

37

N
.
K(K − 1)

(91)

In the delivery phase, we can send the following coded data batch:
M

j∈[1:K]

∪i∈[1:K]\j A[1:K]\{i,j} (i; j),

(92)

L
which is useful for the K workers in the same time as follows: wk has j∈[1:K]\k ∪i∈[1:K]\j A[1:K]\{i,j} (i; j)
which it can subtract to recover the needed part ∪i∈[1:K]\k A[1:K]\{i,k} (i; k). Moreover, the size of
the coded transmission in (92) is the same as the size of the uncoded elements given in (91) as
N
N
N
K(K−1) , which achieves the pair (S = (K − 1) K , Rworst-case = K(K−1) ).

D.3

Closing the Gap for m = K − 2

N
For the storage point m = K − 2 (S = (K − 2) K
), whenever a data point is newly assigned to


(K−2)(K−1)
(K−1)(K−2)
K−2
a worker, it already has K−4 =
out of K−1
parts, and hence only
2
K−3 =
2
2d
K − 2 parts are needed of size (K−1)(K−2) bits each. We also assume the worst-case scenario, where
according to Corollary 5 every worker is assigned completely new data batch, i.e., Si,i = 0 and
N
new data points for all i ∈ [1 : K]. Therefore, the total number of sub-points
worker wi needs K
N
needed by every worker is (K − 2) K
.
• Consider the data sub-points which are considered interference to wk (neither available nor
needed). First, wk does not need nor previously assigned the data points in the batches A(i; j)
where i 6= j and i, j ∈ [1 : K] \ k (potential interference). However, not the whole data points in
A(i; j) are sent to wj , since wj has already some parts of them, which are given by AW (i; j), where
j ∈ W and |W| = K − 3. Moreover, wk also has some parts available in its cache of A(i; j) given
by AW (i; j), where k ∈ W (do not cause interference). As a summary, the part of A(i; j), where
i 6= j and i, j ∈ [1 : K] \ k, that is considered interference to wk is given by A[1:K]\{i,j,k} (i; j), and
hence the total interference faced by wk is

I(k) =

∪

i,j∈[1:K]\k
i6=j

A[1:K]\{i,j,k} (i; j).

(93)

• Next, we organize these interference sub-batches according to the workers that need them as in
Figure 7a. Worker wj , where j ∈ [1 : K] \ k, needs the following sub-batches causing interference
to wk :
I(j; k) =

∪

which consists of data sub-points of size
Ij;k =

X

i∈[1:K]\{k,j}

A[1:K]\{i,j,k} (i; j),

(94)

i∈[1:K]\{k,j}

2d
(K−1)(K−2)

each and total number given by

Si,j = N/K − Sk,j =

X

Sk,i .

(95)

i∈[1:K]\{k,j}

Note that I(j; k) serves as: a) interference to wk , b) useful for wj ; and c) available at all the remaining workers. Also, the total interference faced by wk can be written as I(k) = ∪j∈[1:K]\k I(j; k)
38

X

j62{1,k} Sk,j

sub-points

I(1; k)
X

X

I(2; k)

j62{2,k} Sk,j

sub-points

I(i; k)

X

(a)

j62{K,k} Sk,j

sub-points
I(K; k)

j62{i,k} Sk,j

sub-points

w1

...

w2

wi

...

Sk,i

I (i) (2; k)

Available
at wi

Sk,i

sub-points

C (i) (k)

(b)

...

w2

...

wi

wK
Sk,i

+

sub-points I (i) (1; k)

w1

...

wk

sub-points
I (i) (K; k)

Sk,i aligned
interference
symbols

...

wk

wK

Figure 7: In (a), the interference sub-batches seen by wk are organized according to the workers
that need them, such that I(i; k) for i 6= k is the data needed to be delivered to wi while causing
interference to wk . In (b), we pick Sk,i sub-points from each I(j; k) (labeled as I (i) (j; k)) where
j 6∈ {i, k}, and align them into Sk,i coded symbols labeled by the set C (i) (k), which serve as aligned
interference for wk , available at wi , and useful for the remaining workers.

which consists of data sub-points of size
Ik =

X

Ij;k =

j∈[1:K]\k

2d
(K−1)(K−2)

X

j∈[1:K]\k

each and total number given by

(N/K − Sk,j ) = (K − 2)

N
.
K

(96)

• Following Example 3, we apply a similar interference alignment argument. We first break I(j; k)
for every j ∈ [1 : K] \ k into K − 2 partitions labeled as I (i) (j; k) for i ∈ [1 : K] \ {j, k}. The
number of sub-points in I (i) (j; k) is Sk,i which satisfies the total size of I(j; k) given in (95). As
shown in Figure 7b, we generate Sk,i coded sub-points for every i ∈ [1 : K] \ k as follows:
Sk,i coded sub-points :

C (i) (k) =

M

j∈[1:K]\{k,i}

I (i) (j; k),

∀i ∈ [1 : K] \ k.

(97)

Note that C (i) (k) is a coded sub-batch serves as: a) aligned interference to wk , b) available at wi
as j 6= i in the above summation; and c) useful for all the remaining workers as follows: worker
L
w` for ` 6∈ {i, k} has j∈[1:K]\{k,i,`} I (i) (j; k) so it can subtract from C (i) (k) to get the needed part
I (i) (`; k).
P
N
coded sub-points, which aligns the Ik =
• The total size of ∪i∈[1:K]\k C (i) (k) is i∈[1:K]\k Sk,i = K
N
N
(K − 2) K total interference sub-points seen by wk , i.e., I(k) into K
coded sub-points. In the same
P
N
time, these K coded sub-points serve, for each remaining worker wj for j 6= k, as i∈[1:K]\{j,k} Sk,i =
N
(i)
K − Sk,j useful sub-points given by ∪i∈[1:K]\{k,j} C (k), while the remaining Sk,j sub-points, given
by C (j) (k), are available at wj ’s cache.
• By aligning all the interference seen by all the workers, i.e., generating the coded batches
39

∪i∈[1:K]\k C (i) (k) for all k ∈ [1 : K], we get a total number of N coded sub-points seen as follows by
P
N
N
every worker wj : a) K
aligned interference coded sub-points, b) k∈[1:K]\j Sk,j = K
available sub
P
N
N
points; and c) k∈[1:K]\j K − Sk,j = (K −2) K useful sub-points, which satisfies the total number
of sub-points needed in the worst case as discussed in the beginning. Since out of all the N coded
N
sub-points every worker already has K
of them, then the N coded sub-points can be sent in only
2d
N
each, where the interference sub-points
(K−1) K linear independent combinations of size (K−1)(K−2)
N
N
occupy K dimensions, while the useful sub-points occupy (K − 2) K
dimensions. As a result, the
2N
2N
N
, Rworst-case = K(K−2)
total rate achieved is K(K−2) d bits, which achieves the pair (S = (K − 2) K
).
N
Now that we have closed the gap between the bounds in Theorems 1 and 2 for S = m K , where
m ∈ {1, K − 2, K − 1}, which covers all the storage values for K < 5, while for K ≥ 5 we can do
the same analysis as in Section C to obtain the gap ratio similar to (84) as follows:
upper
1
Rworst-case
=1+
lower
K −j
Rworst-case



(K + 1)(j − 1)
2
1−
=1+
,
(K − 1)(j + 1)
(K − 1)(j + 1)

which is maximized for j = 2 to obtain the maximum gap ratio as 1 +
which completes the proof of Theorem 4.

40

j ∈ [2 : K − 1],

2
(K−1)(3)

=

K− 13
K−1

(98)

for K ≥ 5

