Order optimal task allocation in distributed computing via interweaved cliques

We consider a distributed computing system in which a master node coordinates N workers to evaluate a function over n input files, where this function accepts general decomposition. In particular, we focus on the general case where the requested function admits a d-uniform decomposition, meaning that it can be decomposed into a set of subfunctions that each depends on a unique d-tuple of the n files. Our objective is to design file and task allocations that minimize the worst-case communication from the master to any worker and the worstcase computational load across workers. We first show that the optimal file and task allocation with minimum communication and computation costs admits a natural characterization within combinatorial design theory: it corresponds to a Steiner system S(t, k, v) with t = d, v = n, and k ≈ n N1/d . However, Steiner systems are known to exist only for very restricted parameter regimes. To overcome this limitation, we propose the informationtheoretic-inspired Interweaved Clique (IC) design, a universal and deterministic allocation framework that relaxes the strict structure of Steiner systems by allowing slight variations in worker file loads. Although slightly suboptimal, the IC design achieves a communication cost within a constant factor 4e from our converse, while also maintaining an order-optimal computation cost, thus allowing this work to derive the fundamental scaling laws of this general distributed computing problem for a large range of parameters.