Fundamental limits of distributed computation over networks

Large-scale distributed computing systems, such as MapReduce, Spark, or distributed deep networks, are critical for parallelizing the execution of computational tasks. Nevertheless, a struggle between computation and communication complexity lies at the heart of distributed computing. There has been recently a substantial effort to address this problem for a class of functions, such as distributed matrix multiplication, distributed gradient coding, linearly separable functions, and beyond. In this tutorial, we will discuss the key methods devised to understand the fundamental tradeoff between communication and computation complexities. In the first part of the tutorial, we will unveil information and graph-theoretic approaches to resolve some well-known distributed coding and communication problems, allowing for lowered communication complexity and even for a) correlated data, b) a broad class of functions, and c) well-known topologies. In the second part of the tutorial, we will detail coding theoretic techniques, allowing for the evaluation of the joint behavior of the communication and computation costs, storage, and recovery thresholds, motivated by the same challenge in the complexities.