Coded caching and distributed computing: Opportunities and challenges

Ramamoorthy, Aditya; Elia, Petros
ITW 2018, Information Theory Workshop, 25-29 November 2018, Guangzhou, China

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.


Type:
Tutorial
City:
Guangzhou
Date:
2018-11-25
Department:
Communication systems
Eurecom Ref:
5744
Copyright:
© 2018 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

PERMALINK : https://www.eurecom.fr/publication/5744