Fundamental limits of multi-user distributed computing of linearly separable functions

This work establishes the fundamental limits of the classical problem of multi-user distributed computing of linearly separable functions. In particular, we consider a distributed computing setting involving L users, each requesting a linearly separable function over K basis subfunctions from a master node, who is assisted by N distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to M subfunctions, and each server can communicate linear combinations of their locally computed subfunctions’ outputs to at most ∆ users. The objective is to design a distributed computing scheme that reduces the communication cost (total amount of data from servers to users), and towards this, for any given K, L, M, and ∆, we propose a distributed computing scheme that jointly designs the task assignment and transmissions, and shows that the scheme achieves optimal performance in the real field under various conditions using a novel converse. We also characterize the performance of the scheme in the finite field using another converse based on counting arguments.