A Caltech Library Service

Distributed Storage Allocations

Leong, Derek and Dimakis, Alexandros G. and Ho, Tracey (2012) Distributed Storage Allocations. IEEE Transactions on Information Theory, 58 (7). pp. 4733-4752. ISSN 0018-9448. doi:10.1109/TIT.2012.2191135.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We examine the problem of allocating a given total storage budget in a distributed storage system for maximum reliability. A source has a single data object that is to be coded and stored over a set of storage nodes; it is allowed to store any amount of coded data in each node, as long as the total amount of storage used does not exceed the given budget. A data collector subsequently attempts to recover the original data object by accessing only the data stored in a random subset of the nodes. By using an appropriate code, successful recovery can be achieved whenever the total amount of data accessed is at least the size of the original data object. The goal is to find an optimal storage allocation that maximizes the probability of successful recovery. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models. The optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) are determined for a variety of cases. Our results indicate that the optimal allocations often have nonintuitive structure and are difficult to specify. We also show that depending on the circumstances, coding may or may not be beneficial for reliable storage.

Item Type:Article
Related URLs:
Additional Information:© 2012 IEEE. Manuscript received November 18, 2010; revised December 13, 2011; accepted February 29, 2012. Date of publication March 15, 2012; date of current version June 12, 2012. The work of D. Leong and T. Ho was supported in part by Subcontract 069153 issued by BAE Systems National Security Solutions, Inc., by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego, CA, under Contract N66001-08-C-2013, by the Air Force Office of Scientific Research under Grant FA9550-10-1-0166, and by the California Institute of Technology (Caltech) Lee Center for Advanced Networking. The work of D. Leong was supported in part by A*STAR, Singapore. The work of A. G. Dimakis was supported in part by the Caltech Center for the Mathematics of Information, and by the National Science Foundation under Grant 1055099. The material in this paper was presented in part at the Workshop on Network Coding, Theory, and Applications, Lausanne, Switzerland, June 2009 [1], the 2010 IEEE International Conference on Communications [2], and the 2010 IEEE Global Communications Conference [3].
Funding AgencyGrant Number
BAE Systems National Security Solutions, Inc.069153
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Space and Naval Warfare System Center (SPAWARSYSCEN)N66001-08-C-2013
Air Force Office of Scientific Research (AFOSR)FA9550-10-1-0166
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Caltech Center for the Mathematics of InformationUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12804370
Issue or Number:7
Record Number:CaltechAUTHORS:20120716-093559713
Persistent URL:
Official Citation:Leong, D.; Dimakis, A.G.; Ho, T.; , "Distributed Storage Allocations," Information Theory, IEEE Transactions on , vol.58, no.7, pp.4733-4752, July 2012 doi: 10.1109/TIT.2012.2191135 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:32458
Deposited By: Tony Diaz
Deposited On:16 Jul 2012 17:21
Last Modified:09 Nov 2021 21:27

Repository Staff Only: item control page