DocumentCode :
3604939
Title :
Storage Capacity of Repairable Networks
Author :
Mazumdar, Arya
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Minnesota, Minneapolis, MN, USA
Volume :
61
Issue :
11
fYear :
2015
Firstpage :
5810
Lastpage :
5821
Abstract :
In this paper, we introduce a model of a distributed storage system that is locally recoverable from any single server failure. Unlike the usual local recovery model of codes for distributed storage, this model accounts for the fact that each server or storage node in a network is connectable to only some, and not all other, nodes. This may happen for reasons such as physical separation, inhomogeneity in storage platforms, and so forth. We estimate the storage capacity of both undirected and directed networks under this model and propose some constructive schemes. From a coding theory point of view, we show that this model is approximately dual of the well-studied index coding problem. Furthermore, in this paper, we extend the above model to handle multiple server failures. Among other results, we provide an upper bound on the minimum pairwise distance of a set of words that can be stored in a graph with the local repair guarantee. The well-known impossibility bounds on the distance of locally recoverable codes follow from our result.
Keywords :
directed graphs; network coding; telecommunication network reliability; coding theory; directed network; distributed storage system; index coding problem; locally recoverable code; multiple server failure handling; repairable network storage capacity; undirected network; Approximation methods; Channel coding; Decoding; Indexes; Network coding; Servers; Locally repairable codes; distributed storage; graph capacity; index coding;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2015.2472521
Filename :
7222436
Link To Document :
بازگشت