Graph Theoretic Analysis of Distributed Storage Capacity

21 concepts15 papers1 proposal

In large-scale distributed storage systems, hardware failures are a certainty rather than an exception. To prevent data loss, systems introduce redundancy. Historically, this meant simple replication or erasure coding. However, when a storage node fails, replacing it requires downloading data across the network—a process known as node repair that can severely bottleneck system bandwidth.

To optimize these systems, researchers have turned to graph theory. By mapping the physical and temporal realities of data storage, node failures, and network communications onto graph structures, we can transform complex distributed systems problems into well-understood combinatorial optimization problems. This approach allows us to determine exactly how much information a network can store and how efficiently it can be repaired.

Mapping Network Dynamics to Information Flow Graphs

The foundational tool in this domain is the information flow graph, introduced by Alex Dimakis et al. in Network Coding for Distributed Storage Systems. The core challenge of modeling a distributed storage system is that it is dynamic: nodes fail and are replaced by new nodes over time. An information flow graph resolves this by representing the system as a directed acyclic graph (DAG) that tracks the history of the data.

In this graph, each physical storage node is represented by two vertices: an in-node ($x_{in}$) and an out-node ($x_{out}$). A directed edge connects $x_{in}$ to $x_{out}$ with a capacity equal to the node's storage limit. This split is crucial because it decouples a node's internal storage capacity from its external network communication. When a node fails and a new node is introduced to replace it, the new node's $x_{in}$ receives directed edges from the $x_{out}$ vertices of the surviving helper nodes. The capacity of these incoming edges corresponds to the repair bandwidth allocated from each helper.

[Helper Node Out] ---> (Repair Bandwidth Edge) ---> [New Node In] ---> (Storage Capacity Edge) ---> [New Node Out]

To find the maximum file size that can be reliably stored, we imagine a "data collector" node that connects to a subset of active storage nodes to reconstruct the original file. By applying the classic max-flow min-cut theorem to this graph, Alex Dimakis et al. demonstrated that the storage capacity is strictly bounded by the minimum cut separating the original data source from the data collector. As surveyed by Alex Dimakis et al. in A Survey on Network Codes for Distributed Storage, this framework underpins the design of regenerating codes, which minimize repair traffic by treating repair as a network flow problem rather than a simple data reconstruction task.

Accounting for Real-World Topologies: Racks and Clusters

While early models assumed a homogeneous network where any node could talk to any other node with equal cost, real-world data centers are hierarchical. Nodes are organized into racks or clusters, where communication within a rack is cheap, but cross-rack traffic is highly constrained and expensive.

To capture this asymmetry, the information flow graph can be augmented with intermediate cluster or rack nodes. For instance, Hanxu Hou et al. utilized directed acyclic information flow graphs in Rack-Aware Regenerating Codes for Data Centers to model rack-aware regenerating codes, mathematically characterizing the exact trade-offs between local storage and cross-rack communication. Similarly, Jy-yong Sohn et al. applied min-cut analysis to clustered architectures in Capacity of Clustered Distributed Storage, deriving closed-form expressions for storage capacity as a direct function of intra-cluster and cross-cluster bandwidth limits.

This structural mapping extends to other constrained environments. Toni Ernvall et al. extended this to heterogeneous networks in Capacity and Security of Heterogeneous Distributed Storage Systems, proving that symmetric repair remains optimal even when node capacities vary. In wireless edge scenarios, Nitish Mital et al. applied min-cut analysis to information flow graphs in Storage-Repair Bandwidth Trade-off for Wireless Caching with Partial Failure and Broadcast Repair to optimize broadcast-based repair schemes. By embedding physical topology constraints directly into the graph's edge capacities, the min-cut bound automatically reveals the fundamental limits of the underlying physical architecture, as further demonstrated by Jingzhao Wang et al. in Storage and Repair Bandwidth Tradeoff for Distributed Storage Systems with Clusters and Separate Nodes and Ying Miao et al. in Repairing Schemes for Tamo-Barg Codes.

Storage Capacity as a Combinatorial Vertex Cover

When network connectivity is strictly localized—meaning nodes can only communicate with their immediate neighbors in a fixed graph topology—the problem shifts from network flow to combinatorial graph invariants. In Storage Capacity of Repairable Networks, Arya Mazumdar established a deep connection between a network's storage capacity under local repair constraints and two classic graph-theoretic concepts: the minimum vertex cover and the maximum matching.

Consider a network modeled as an undirected graph where vertices are storage servers and edges represent direct communication links. If we require that any single node failure must be repairable by downloading data exclusively from its immediate neighbors, how much total data can the network store?

The maximum information a network can store under these conditions is fundamentally bounded by the size of its minimum vertex cover. A vertex cover is a set of vertices that touches every edge in the graph. In Storage Capacity as an Information-Theoretic Analogue of Vertex Cover, Arya Mazumdar et al. demonstrated that the minimum vertex cover acts as an information-theoretic upper bound because any data stored outside the vertex cover cannot be safely insulated against localized failures without violating repair constraints.

To find tighter bounds for complex graph families, the authors introduced a technique called gadget covering. Instead of relying on a single global vertex cover, gadget covering constructs specific local vertex sets across subgraphs (gadgets), calculates their individual vertex covers, and averages them. This combinatorial averaging exploits local structural symmetries to produce significantly tighter upper bounds on storage capacity than standard single-cover methods.

Conversely, the maximum matching—a set of edges sharing no common vertices—provides a constructive lower bound. Arya Mazumdar showed that by simply mirroring data across the independent edges of a maximum matching, a system can reliably achieve at least half of the theoretical maximum storage capacity. Because both maximum matchings and vertex covers can be efficiently analyzed using polynomial-time algorithms, this equivalence allows engineers to bypass intractable information-theoretic calculations and design optimal storage layouts using pure graph theory, a connection further detailed by Arya Mazumdar et al. in Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate.

Broader Applications: Privacy, Security, and Service Capacity

The utility of graph-theoretic modeling extends beyond capacity and repair trade-offs into privacy, security, and download throughput:

Key Foundational Work

Network Coding for Distributed Storage Systems. (2007) — contributed 2 concept elements to this direction.
Network Coding for Distributed Storage Systems (2007) — contributed 1 concept elements to this direction.
A Survey on Network Codes for Distributed Storage. (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_information_flow_graph_analysis_751f1813,
  title = {information flow graph analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-flow-graph-analysis/rdr_751f18131c3541648779dc561d855d33},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_information_flow_graph_analysis_751f1813_v1,
  title = {information flow graph analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-flow-graph-analysis/rdr_751f18131c3541648779dc561d855d33/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake