Update-efficient codes for erasure correction

Abstract

The problem of designing codes to protect against server failures in a distributed storage system for frequently changing data is considered. When the original data changes, the coded packets stored on the servers must be updated accordingly. Since performing updates consumes costly bandwidth and energy, it is of interest to construct codes that have small update complexity, which we define as the maximum number of coded symbols that must be updated when any single information symbol is changed. Linear codes which are conventionally used or recently proposed for use in storage systems for correcting a linear number of erasures (such as Reed-Solomon and other MDS codes) have the update complexity which scales linearly with the code length. In this paper, we take advantage of randomization to construct update-efficient codes that have update complexity scaling sub-linearly with the code length. Two erasure models are examined: random erasures (i.e., the erasure channel) and adversarial erasures.