Latency-Optimal Geo-Distributed Storage over Structured Networks
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 ≥ 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.
Related
- Optimisation of distributed storage in existing district heating networks to solve hydraulic bottlenecks
- Distributed Stochastic Extremum Seeking for Optimal Resource Allocation over Networks with Time Delays
- Structured Positive-Definite Optimal Control Synthesis of Closed-Loop Recommendation Systems over Social Networks
- Low-Latency Coded Tensor--Matrix Multiplication for Distributed Signal Processing Systems
- Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys
BibTeX
@misc{pathegama2026latencyoptimal,
title = {{Latency-Optimal Geo-Distributed Storage over Structured Networks}},
author = {Madhura Pathegama and Viveck Cadambe},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05229},
eprint = {2609.05229},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05229},
}
RIS
TY - UNPB
TI - Latency-Optimal Geo-Distributed Storage over Structured Networks
AU - Madhura Pathegama
AU - Viveck Cadambe
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05229
UR - https://arxiv.org/abs/2609.05229
AB - 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 ≥ 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.
ER -