On the Worst-case Communication Overhead for Distributed Data Shuffling
  Distributed learning platforms for processing large scale data-sets are
becoming increasingly prevalent. In typical distributed implementations, a
centralized master node breaks the data-set into smaller batches for parallel
processing across distributed workers to achieve speed-up and efficiency.
Several computational tasks are of sequential nature, and involve multiple
passes over the data. At each iteration over the data, it is common practice to
randomly re-shuffle the data at the master node, assigning different batches
for each worker to process. This random re-shuffling operation comes at the
cost of extra communication overhead, since at each shuffle, new data points
need to be delivered to the distributed workers.
  In this paper, we focus on characterizing the information theoretically
optimal communication overhead for the distributed data shuffling problem. We
propose a novel coded data delivery scheme for the case of no excess storage,
where every worker can only store the assigned data batches under processing.
Our scheme exploits a new type of coding opportunity and is applicable to any
arbitrary shuffle, and for any number of workers. We also present an
information theoretic lower bound on the minimum communication overhead for
data shuffling, and show that the proposed scheme matches this lower bound for
the worst-case communication overhead.
