{
  "annotation_id": "4d0851bd-43b8-4d93-9c34-68c879f49f0b",
  "date_created": "2026-02-17T05:53:04.949000Z",
  "date_modified": "2026-02-17T05:53:04.949000Z",
  "file_hash": "1874e535b0f2b1d82f45767c3fe6c324252acbc0c49f780b111cafb0a5f0f0bf",
  "private": false,
  "record": {
    "abstract": "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 $\\mathbf{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 $\\mathbf{X}$, that minimizes the communication cost $\\pi_{\\mathbf{X}}$, representing the maximum number of distinct files per server, while also minimizing the computation cost $\\delta_{\\mathbf{X}}$ corresponding to a maximal worker subfunction load. For a broad range of parameters, we propose a deterministic allocation solution, the \\emph{Interweaved-Cliques (IC) design}, whose information-theoretic-inspired interweaved clique structure simultaneously achieves order-optimal communication and computation costs, for a large class of decompositions $\\mathbf{X}$. This optimality is derived from our achievability and converse bounds, which reveal -- under reasonable assumptions on the density of $\\mathbf{X}$ -- that the optimal scaling of the communication cost takes the form $n/N^{1/d}$, revealing that our design achieves the order-optimal \\textit{partitioning gain} that scales as $N^{1/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 $\\mathbf{X}$, therefore enabling multiple desired functions to be computed without reshuffling files.",
    "arxiv_id": "2601.05873",
    "authors": [
      "Javad Maheri",
      "K. K. Krishnan Namboodiri",
      "Petros Elia"
    ],
    "categories": [
      "cs.IT",
      "math.IT"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "Universal and Asymptotically Optimal Data and Task Allocation in Distributed Computing",
    "url": "https://arxiv.org/abs/2601.05873",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e232c942-441a-4313-9074-63a920d55056",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}