Capacity bounds for distributed storage

Michael Luby

Published 2016-10-11Version 1

The information capacity of a distributed storage system is the amount of source data that can be reliably stored for long durations. Storage nodes fail over time and are replaced, and thus data is erased at an erasure rate. To maintain recoverability of source data, a repairer generates redundant data from data read from nodes, and writes redundant data to nodes, where the repair rate is the rate at which the repairer reads and writes data. We prove the information capacity approaches (1-1/(2*sigma))*N*s as N and sigma grow, where N is the number of nodes, s is the amount of data each node can store, and sigma is the repair rate to erasure rate ratio.