Update-efficient codes for erasure correction

N. Prasanth Anthapadmanabhan, Emina Soljanin, Sriram Vishwanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Pages376-382
Number of pages7
DOIs
StatePublished - 2010
Externally publishedYes
Event48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 - Monticello, IL, United States
Duration: Sep 29 2010Oct 1 2010

Publication series

Name2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

Other

Other48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Country/TerritoryUnited States
CityMonticello, IL
Period9/29/1010/1/10

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Update-efficient codes for erasure correction'. Together they form a unique fingerprint.

Cite this