This tutorial will bring together the exciting areas of information-theoretic caching and distributed computing, and will discuss powerful ways in which advanced coding can exploit the deep connections between memory, communication and computing. Current research is at a juncture where the massive potential gains from jointly tapping into these three resources is evident. However, it is well understood that the gains are massively limited by fundamental bottlenecks. This requires, not only addressing these bottlenecks head on, but also exploring some of these ideas in a variety of new settings and topologies. The tutorial will explore the role of information theory and coding, in meeting the fundamental performance limits in a variety of such pertinent settings, as well as their role in resolving some of these bottlenecks. Furthermore, we will discuss how the consideration of alternate settings may complement and even accentuate the original gains.
We will first consider recent advances in information-theoretic coded caching, demonstrating the tremendous benefits of applying coding techniques to the caching problem, for a variety of wired as well as wireless settings. In this context, we will offer a top level overview of caching, with a detailed discussion of the underlying coding machinery, offering explanations of the achievable schemes, discussing the corresponding outer bounds, and highlighting more recent results as well as opportunities for future work.
The tutorial will then discuss the basics of distributed computing, and outline the coding connections that connect computing with caching. We will focus on the basic Map Reduce paradigm and demonstrate that information-theoretic approaches allow us to operate on a natural computation vs. communication trade-off. In particular, we will offer a detailed discussion of how judicious placement of tasks on computation nodes along with coded transmission in the shuffle phase, benefits job execution times.
The overall discussion will outline a unified view of the biggest challenges that appear in both these domains that can be key obstacles to realizing the promised gains. In the final part of the tutorial we will present an in-depth discussion of interesting directions based on combinatorics and graph theory for their resolution.