Technical Report CS0779

Authors: M. Naor and R.M. Roth

The following file distribution is considered: Given a network of processors represented by an undirected graph G = (V,E), and a file size k, and arbitrary file 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 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 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 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion