Universal and asymptotically optimal data and task allocation in distributed computing

We study the joint minimization of communication and computation costs in distributed computing, where a master node coordinates N workers to evaluate a function over a library of n files. Assuming that the function is decomposed into an arbitrary subfunction set X, with each subfunction depending on d input files, renders our distributed computing problem into a d-uniform hypergraph edge partitioning problem wherein the edge set (subfunction set), defined by d-wise dependencies between vertices (files) must be partitioned across N disjoint groups (workers). The aim is to design a file and subfunction allocation, corresponding to a partition of X, that minimizes the communication cost πX, representing the maximum number of distinct files per server, while also minimizing the computation cost δX corresponding to a maximal worker subfunction load. For a broad range of parameters, we propose a deterministic allocation solution, the Interweaved-Cliques (IC) design, whose informationtheoretic-inspired interweaved clique structure simultaneously achieves order-optimal communication and computation costs, for a large class of decompositions X. This optimality is derived from our achievability and converse bounds, which reveal — under reasonable assumptions on the density of X —that the optimal scaling of the communication cost takes the form n/N1/d, revealing that our design achieves the order-optimal partitioning gain that scales as N1/d, while also achieving an order-optimal computation cost. Interestingly, this order optimality is achieved in a deterministic manner, and very importantly, it is achieved blindly from X, therefore enabling multiple desired functions to be computed without reshuffling files.