OPTIMAL FILE SHARING IN DISTRIBUTED NETWORKS

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 w of k bits is to be distributed among all n odes of G. To this end, each node is assigned a memory device such tha t by accessing the memory of its own and of its adjacent nodes, the no de can reconstruct the contents of w. The objective is to minimize the total size of memory in the network. This paper presents a file distr ibution scheme which realizes this objective for k much greater than l og Delta(G), where Delta(G) stands for the maximum degree in G: For th is 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 tv into the nod e memory devices, can be computed in time complexity which is polynomi al in k and \V\. Furthermore, each node can reconstruct the contents o f such a file w in O(k(2)) bit operations. Finally it is shown that th e requirement of k being much larger than log Delta(G) is necessary in order to have total memory size close to the integer programming lowe r bound.