GDSP: A graphical perspective on the distributed storage systems

Saeid Sahraei, Michael Gastpar

Abstract: The classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vertices associated with it. This paper considers the generalization of this problem to arbitrary hyper-graphs and to the case of multiple files, where each user is only interested in one, a problem we will refer to as the graphical distributed storage problem (GDSP). Specifically, we make progress in the analysis of minimum-storage codes for two main subproblems of the GDSP which extend the classical model in two independent directions: the case of an arbitrary graph with multiple files, and the case of an arbitrary hyper-graph with a single file.

Introduction and Problem Formulation

In the classical Distributed Storage Problem (DSP), the standard assumption is a "complete" setup: any subset of $k$ servers out of a total $K$ must be able to reconstruct a file. In graph-theoretic terms, this is represented as a complete $k$-uniform hypergraph. While this model provides strong theoretical bounds, real-world networks are rarely so uniform. Physical constraints, such as geographical distance, network hierarchy, and varying server reliability, mean that users (represented by edges) often only have access to specific subsets of servers.

Furthermore, modern distributed systems must handle multiple files simultaneously, where different users may request different content. To address these complexities, this paper introduces the Graphical Distributed Storage Problem (GDSP). The core question of GDSP is: What is the minimum total memory needed across all servers to satisfy a specific set of user requests, where each request is defined by a subset of servers and a specific file?

The general model of the Graphical Distributed Storage Problem (GDSP), mapping servers (X) to user requests (Z).

Methodology

The paper decomposes the GDSP into two primary sub-problems to analyze the storage limits and optimal coding strategies.

1. Multiple Files on Arbitrary Graphs

The authors focus on scenarios where each user connects to exactly two servers. They introduce the concept of Smoothly Colored Graphs. These networks are partitioned into clusters (e.g., regional data centers) where the majority of requests are internal to a cluster. Inter-cluster requests are governed by strict "smoothness" rules regarding how they bridge different regions.

To solve this, the paper proposes Algorithm 1 (Superposition Algorithm). This divide-and-conquer strategy breaks the complex multi-file graph into simpler sub-graphs—one for each file or "color." The algorithm solves these sub-problems independently and then "superposes" (sums) the memory allocations to find the total storage requirement.

A 15-node clustered graph illustrating the concept of smoothly colored graphs and regional file interests.

2. Single File on Arbitrary Hypergraphs

In cases where all users request the same file but access patterns are arbitrary (hyper-edges of varying sizes), the problem is mapped to a single-source network information flow problem. This allows the authors to leverage tools from network coding to characterize the storage budget.

Key Insights and Theoretical Results

The Optimality of Superposition

A major contribution of this work is proving that for "smoothly colored" networks, solving for each file individually and summing the results is actually optimal. This is a non-trivial finding because, in general multi-file systems, joint coding across different files could potentially reduce the total storage footprint. The paper demonstrates that optimality depends heavily on the "boundary" of the clusters; if the sets of vertices connecting different clusters are disjoint, the problem simplifies significantly.

Linear Programming Characterization

For the single-file hypergraph case, the authors show that the minimum storage budget $M^*$ is exactly the solution to a Linear Programming (LP) problem. This establishes a direct connection between GDSP and the min-cut max-flow theorem in network coding, where the sum of memories in any hyper-edge (user access set) must be at least 1.

Limits of Independence

While superposition is powerful, it is not universal. The authors provide a counter-example showing that if "smoothness" conditions are violated, independent coding for each file becomes strictly sub-optimal. In such non-smooth networks, joint coding across files (e.g., combining fragments of different files into a single storage block) is required to reach the theoretical minimum storage. For instance, in one specific model, the superposition approach required a total memory of 13.5, while a joint strategy achieved the same goal with only 12.

Conclusion

The GDSP framework provides a more realistic lens for analyzing distributed storage by incorporating network topology and multi-file requests. While the Superposition Algorithm offers an optimal solution for clustered, smoothly colored graphs, future work is needed to generalize these findings to more complex hypergraphs and to incorporate the trade-off between storage and repair bandwidth.

Summary updated

Abstract

The classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vertices associated with it. This paper considers the generalization of this problem to arbitrary hyper-graphs and to the case of multiple files, where each user is only interested in one, a problem we will refer to as the graphical distributed storage problem (GDSP). Specifically, we make progress in the analysis of minimum-storage codes for two main subproblems of the GDSP which extend the classical model in two independent directions: the case of an arbitrary graph with multiple files, and the case of an arbitrary hyper-graph with a single file.
BibTeX
@misc{sahraei2017gdsp,
  author = {Saeid Sahraei and Michael Gastpar},
  title = {{GDSP: A graphical perspective on the distributed storage systems}},
  year = {2017},
  eprint = {1702.04525},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.04525},
}
Figure