On the Tradeoff Between Computation and Communication Costs for Distributed Linearly Separable Computation

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks N distributed workers to compute a linearly separable function of K datasets, which is a set of K-c linear combinations of K equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any N-r out of N workers the master can recover the task function with high probability. In the literature, the specific case where K-c = 1 or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general K-c and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popular cyclic assignment (widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when K-c is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or K-c is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases.

Automated summary

This paper studies the distributed linearly separable computation problem and proposes a novel distributed computing scheme. By introducing a new conversational bound under the constraint of communication cost, this method achieves optimal performance for specific system parameters.