Journal Article

Optimal File Sharing in Distributed Networks

Roth, Ron M., Naor, Moni

1995

Overview

The following file distribution problem is considered: Given a network of processors represented by an undirected graph $G = (V, E)$ and a file size $k$, an arbitrary file ${\\bf w}$ of $k$ bits is to be distributed among all nodes of $G$. To this end, each node is assigned a memory device such that by accessing the memory of its own and of its adjacent nodes, the node can reconstruct the contents of ${\\bf w}$. The objective is to minimize the total size of memory in the network. This paper presents a file distribution scheme which realizes this objective for $k \\gg \\log \\Delta_{G}$, where $\\Delta_{G}$ stands for the maximum degree in $G$: For this range of $k$, the total memory size required by the suggested scheme approaches an integer programming lower bound on that size. The scheme is also constructive in the sense that given $G$ and $k$, the memory size at each node in $G$, as well as the mapping of any file ${\\bf w}$ into the node memory devices, can be computed in time complexity which is polynomial in $k$ and $|V|$. Furthermore, each node can reconstruct the contents of such a file ${\\bf w}$ in $O(k^{2})$ bit operations. Finally, it is shown that the requirement of $k$ being much larger than $\\log \\Delta_{G}$ is necessary in order to have total memory size close to the integer programming lower bound.

• Publisher: Society for Industrial and Applied Mathematics
• Subject: Algorithmics. Computability. Computer arithmetics / Applied mathematics / Applied sciences / Computer science / Computer science; control theory; systems / Computer systems and distributed systems. User interface / Data processing. List processing. Character string processing / Exact sciences and technology / File sharing / Integer programming / Linear programming / Memory organisation. Data processing / Software / Theoretical computing