# Order Optimal Task Allocation in Distributed Computing via Interweaved Cliques

Source: [Order Optimal Task Allocation in Distributed Computing via Interweaved Cliques](<https://www.sota2.com/research/paper/69e7051b7d0172140ec7f265>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-22T05:23:53.567Z

Authors: Javad Maheri, K. K. Krishnan Namboodiri, Petros Elia

Published: 2026-04-20T13:16:37.000Z

## Abstract

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 worst-case 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 \\approx \\frac{n}{N^{1/d}}$. However, Steiner systems are known to exist only for very restricted parameter regimes. To overcome this limitation, we propose the information-theoretic-inspired \\emph{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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2604.18232>)

[PDF](<https://arxiv.org/pdf/2604.18232.pdf>)
