An Upper Bound On the Size of Locally Recoverable Codes

Abstract

In a {\em locally recoverable} or {\em repairable} code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage node as possible. In this paper, we bound the minimum distance of a code in terms of its length, size and locality. Unlike previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence the Simplex codes are the first example of a optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds.

A shorter version has appeared in IEEE NetCod, 2013

Cited by in corpus (9)

• A family of optimal locally recoverable codes
• Binary Cyclic Codes that are Locally Repairable
• Cooperative Local Repair in Distributed Storage
• Optimal Linear and Cyclic Locally Repairable Codes over Small Fields
• Constructions and Properties of Linear Locally Repairable Codes
• Constructions of Locally Recoverable Codes which are Optimal
• Storage Capacity of Repairable Networks
• On minimum distance of locally repairable codes
• On Binary Matroid Minors and Applications to Data Storage over Small Fields