Optimal Locally Repairable Codes and Connections to Matroid Theory. (arXiv:1301.7693v1 [cs.IT])

from cs.IT updates on arXiv.org http://arxiv.org/abs/1301.7693

Petabyte-scale distributed storage systems are currently transitioning to
erasure codes to achieve higher storage efficiency. Classical codes like
Reed-Solomon are highly sub-optimal for distributed environments due to their
high overhead in single-failure events. {\it Locally Repairable Codes} (LRCs)
form a new family of codes that are repair efficient. In particular, LRCs
minimize the number of nodes participating in single node repairs while
generating small network traffic for repairs. Two large-scale distributed
storage systems have already implemented different types of LRCs: Windows Azure
Storage and the Hadoop Distributed File System RAID used by Facebook. The
fundamental bounds for LRCs, namely the best possible distance for a given code
locality, were recently discovered, but few explicit constructions exist. In
this work, we present an explicit and simple to implement construction of
optimal LRCs, for code parameters previously established only by existence
results. % Our construction is very simple to implement. For the analysis of
the code’s optimality, we derive a new result on the matroid represented by the
code’s generator matrix.



Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s