Source-linked AI summary
Latency-Optimal Geo-Distributed Storage over Structured Networks
Madhura Pathegama, Viveck Cadambe
TL;DR
The paper asks how to minimize average retrieval latency when files are assigned across geo-distributed weighted networks. It establishes hardness for k ≥3 through a domatic-number reduction, then identifies graph classes with efficiently constructible uncoded optimal assignments. These classes include weighted trees, suitable weighted cycles, and unit-weight graphs with sufficiently large minimum degree.
Problem
The paper studies how to compute file assignments minimizing average retrieval latency in geo-distributed storage networks modeled as weighted graphs.
Method
It analyzes greedy assignments and relates their existence to domatic partitions, while proving constructions for several structured graph families.
Results
For every fixed k ≥3, deciding whether a greedy assignment exists is NP-complete and computing an average-latency–minimizing assignment is NP-hard.
Takeaways & Limitations
Weighted trees, weighted cycles with k dividing n, and other specified graph classes admit efficiently constructible greedy assignments that achieve latency-optimal structure.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper formulates average-latency file placement in weighted geo-distributed networks and shows both computational hardness and structured optimal assignments for important graph classes.
- Problem formulation: Geo-distributed storage places original or coded files across weighted-graph nodes, where edge weights represent round-trip communication latency.Retrieval may require contacting other nodes and reconstructing the requested original file.
- Problem formulation: Average latency is the retrieval time averaged uniformly over all node–file pairs.In the four-node example, each pair has latency 0 or 1, yielding average latency 3/4.
- Problem formulation: The example uses three uncoded files and one coded combination, illustrating how coding can support retrieval from nearby nodes.The assignment stores W1, W2, W3, and W1 + W2 + W3 across the four nodes.
- Computational complexity: For every fixed k ≥3, computing a latency-minimizing assignment is NP-hard via a reduction from the NP-hard domatic number problem.The paper asks whether an efficiently computable latency-minimizing assignment exists for a given network graph.
- Structured optimal assignments: Weighted trees, certain weighted cycles, and unit-weight graphs with sufficiently large minimum degree admit uncoded greedy assignments that are latency-optimal.For every node, its k closest selected storage locations, including itself, can store all k original files distinctly.
A. Related Work
The paper distinguishes its average-latency, placement-structure focus from prior work on greedy assignments, system design, worst-case coding metrics, and fault-tolerant storage.
- Prior latency-optimal assignment work: Prior work characterized greedy assignments, studied low average-latency codes under optimal per-node worst-case latency, and incorporated file–node preference weights.The paper states that these works do not address its computational-complexity analysis or structured graph families for k ≥3.
- System-level latency work: System-level studies emphasize resource allocation and protocol optimization rather than fundamental file-placement limits and structure.
- Storage-code research: Graph-constrained storage-code research focuses on worst-case metrics such as repair bandwidth and code distance, whereas this paper studies average-case latency and topology-dependent structure.
- Related storage paradigms: Unlike distributed erasure coding, this work uses redundancy to reduce retrieval latency rather than provide fault tolerance.It also differs from coded caching by considering point-to-point retrieval over weighted network graphs instead of a central broadcast link.
II. SYSTEM MODEL AND LATENCY METRICS
The paper models distributed storage on connected weighted graphs and measures retrieval latency through shortest-path communication delays. It defines greedy assignments that match each node’s nearest-node distance profile and therefore attain the minimum average latency.
- System model: Communication latency between nodes is their minimum-path distance, with strictly positive edge weights and possible relaying through intermediate servers.
- System model: Each of n servers stores one coded file spanning k original files, and retrieval uses contacted coded files plus linear decoding.
- Distance profiles and k-sites: For each node, λ(i)_j denotes the distance to its j-th closest node, with λ(i)_1 = 0 because the node is closest to itself.
- Distance profiles and k-sites: A k-site is any set of k closest nodes to a node, including that node itself.
- Latency lower bound: Retrieving j distinct files requires at least j distinct contacted nodes, producing a lower bound based on the ordered nearest-node latencies.
- Greedy assignments: Greedy assignments minimize average latency and also minimize the p-th power-mean latency and per-node worst-case latency.
- Greedy assignments: A greedy assignment achieves equality in the latency lower bound when every node’s k-site stores one uncoded copy of each original file.
III. HARDNESS OF AVERAGE-LATENCY MINIMIZATION
For every fixed k ≥3, deciding whether a greedy k-file assignment exists is NP-complete, implying NP-hardness of exact average-latency minimization. The proof reduces the domatic number problem to greedy assignment existence.
- An optimal assignment is greedy exactly when the lower bound on average latency is attainable, so greedy-assignment hardness implies NP-hardness of exact minimization.
- For every fixed integer k ≥3, determining whether a weighted network admits a greedy k-file assignment is NP-complete.
- The reduction starts from domatic number and uses unit-weight graphs with minimum degree at least k−1.
- In this setting, a greedy assignment corresponds to partitioning vertices into k classes, each of which is a dominating set.
- The reduction establishes equivalence between dom(G) ≥k and existence of a greedy k-file assignment, while disconnected graphs can be joined using sufficiently large-weight edges.
IV. NETWORKS THAT ADMIT GREEDY ASSIGNMENTS
Although greedy-assignment existence is computationally intractable in general network graphs, weighted trees, suitable weighted cycles, and unit-weight graphs with sufficiently large minimum degree admit efficiently constructible greedy assignments.
- Structured network classes can efficiently admit greedy assignments despite general computational intractability.The identified classes are weighted trees, weighted cycles when k divides n, and unit-weight graphs with sufficiently large minimum degree.
A. Weighted tree networks
Every weighted tree supports a greedy file assignment, constructible in O(n^2) time. The construction processes vertices in a rooted traversal order and preserves distinct files across each k-site.
- Every weighted tree with k ≤n supports a greedy file assignment constructible in O(n^2) time.
- A separator lemma shows that k-site differences across a tree separator lie on their respective sides, enabling an inductive assignment argument.
- The tree is rooted and ordered so each parent precedes its successors, allowing vertices to be processed iteratively.
- Slightly perturbing edge weights resolves nonunique k-sites without invalidating the resulting assignment under the original weights.
- When processing a vertex, unassigned k-site nodes receive the smallest-index files not already used in that k-site, while assigned nodes remain unchanged.
- Induction maintains distinct files on every processed k-site because overlap with the parent k-site is already assigned and the remaining nodes are unassigned.
B. Weighted cycle networks with k dividing n
Weighted cycle networks admit a simple sufficient condition: when k divides n, a greedy k-file assignment exists regardless of edge weights and can be constructed in O(n) time.
- Not all weighted cycles admit greedy assignments, but divisibility of n by k provides a sufficient condition.
- When k divides n, every weighted cycle admits a greedy k-file assignment constructible in O(n) time.
- The construction repeats the k files periodically around the cycle, so each node can choose k consecutive nodes storing distinct files.
C. Unit-weight graphs with large minimum degree
For unit-weight graphs, sufficiently strong minimum-degree conditions guarantee greedy assignments, and these assignments can be constructed efficiently in the stated regime.
- C. Unit-weight graphs with large minimum degree: Minimum-degree conditions in unit-weight graphs guarantee a greedy k-file assignment.The result follows from a domatic-number condition stated for unit-weight graphs.
- C. Unit-weight graphs with large minimum degree: The construction can be performed in polynomial time by computing a domatic partition.
V. DISCUSSION AND FUTURE WORK
The paper identifies several structured graph classes admitting greedy assignments and points to broader topology classes and coding-aware latency algorithms as future directions.
- V. DISCUSSION AND FUTURE WORK: Future work should identify richer network topologies admitting greedy assignments, especially classes reflecting practical geo-distributed deployments.
- V. DISCUSSION AND FUTURE WORK: The broader agenda includes understanding coding’s latency benefits, tightening optimal-average-latency bounds, and developing efficient low-latency algorithms for large networks.