It is shown that for every fixed number of files, computing a latency-minimizing assignment is NP-hard via a reduction from the domatic number problem.
Abstract
We study latency-optimal file assignment in geo-distributed storage systems modeled as weighted graphs, where edge weights represent communication delays and each node stores one (possibly coded) file. Our goal is to minimize the average time required to retrieve an original file, taken uniformly over all nodes and files. We show that for every fixed number of files $k \geq 3$, computing a latency-minimizing assignment is NP-hard via a reduction from the domatic number problem. On the positive side, we identify natural network topologies that admit uncoded, structured optimal assignments in which, for every node, one can choose its $k$ closest nodes, including itself, so that they store distinct original files. We prove that every weighted tree, certain weighted cycles, and unit-weight graphs with sufficiently large minimum degree admit such assignments. For these graph classes, we provide efficient algorithms to construct latency-optimal file assignments.
The deterministic guarantee matches the known fixed-node lower bound, and the matching randomized lower bound are proved, ensuring that both guarantees are optimal on every nondegenerate rooted tree.
Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al.· 3 citations
Spanning structures that must be maintained, not merely rebuilt, underlie sensor fabrics, peer-to-peer overlays, and software-defined networks. We give a complete treatment of distributed minimum-spanning-tree (MST) construction and maintenance built on non-tree-edge (NTE) tracking, which certifies the edges excluded f...
This paper presents a method for graph simplification that aims to improve routing efficiency in large-scale communication networks. The approach identifies rings—linear chains of degree-2 vertices decorated with pendant trees and attached to the rest of the network via two connection points. In the simplified represen...
Bikmetov Dmitry, Prihodko Maxim, Dun-Wei She et al.· 2026 IEEE/CIC International...· 0 citations
A randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions is given, which follows from a simple stability principle for partially dynamic graphs.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
This work proposes a novel topology named the Balanced Sparse Tree (BST), which is a topology characterized by symmetric design and sparse connections, motivated by hypergraph theory and Steiner Systems, and demonstrates the superiority of BST over the state-of-the-art in network scale, latency, bandwidth, and cost.
Shaoteng Liu, Dejun Kong, Huitian Wang et al.· Conference on Applications,...· 0 citations
Content placement can substantially reduce peaktime network load by creating coded multicast opportunities, but classical formulations typically assume that placement is free. Under the placement-cost model $c_{r}=\rho r^{\alpha}$ with the nonew-peak constraint, the optimal scheme is known in closed form when user stor...
Yousef Alhassoun· International Symposium on N...· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduOct 6, 2026
Jennifer Neville did not want to go into computer science—but that’s exactly where she landed. Neville discusses the starts and stops that led to her professional sweet spot and her work identifying “surprising failures” making it hard for AI to handle complexity. The post What AI gets wrong and what failure teaches us appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduOct 2, 2026
