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.
Fundamental limits of distributed computation over networks
SPAWC 2024, 25th IEEE International Workshop on Signal Processing Advances in Wireless Communications, 10-13 September 2024, Lucca, Italy
Type:
Tutorial
City:
Lucca
Date:
2024-09-10
Department:
Systèmes de Communication
Eurecom Ref:
7636
Copyright:
© 2024 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.
See also:
PERMALINK : https://www.eurecom.fr/publication/7636