On region-based fault tolerant design of distributed file storage in networks

Distributed storage of data files in different nodes of a network enhances the reliability of the data by offering protection against node failure. In the (N,K),N ≥ K file distribution scheme, from a file F of size |F|, N segments of size |F|/K are created in such a way that it is possible to reconstruct the entire file, just by accessing any K segments. For the reconstruction scheme to work it is essential that the K segments of the file are stored in nodes that are connected in the network. However in case of node failures the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially-correlated or region-based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The goal of this research is to devise a file segment distribution scheme so that, even if the network becomes disconnected due to any region fault, at least one of the largest connected components will have at least K distinct file segments with which to reconstruct the entire file. The distribution scheme will also ensure that the total storage requirement is minimized. We provide an optimal solution through Integer Linear Programming and an approximation solution with a guaranteed performance bound of O(ln n) to solve the problem for any arbitrary network. The performance of the approximation algorithm is evaluated by simulation on two real networks.