2013/05/14 by Arya Mazumdar, Mazumdar, Arya, Venkat Chandar +3 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.1305.3224
Motivated by distributed storage applications, we investigate the degree to\nwhich capacity achieving encodings can be efficiently updated when a single\ninformation bit changes, and the degree to which such encodings can be\nefficiently (i.e., locally) repaired when single encoded bit is lost.\n Specifically, we first develop conditions under which optimum\nerror-correction and update-efficiency are possible, and establish that the\nnumber of encoded bits that must change in response to a change in a single\ninformation bit must scale logarithmically in the block-length of the code if\nwe are to achieve any nontrivial rate with vanishing probability of error over\nthe binary erasure or binary symmetric channels. Moreover, we show there exist\ncapacity-achieving codes with this scaling.\n With respect to local repairability, we develop tight upper and lower bounds\non the number of remaining encoded bits that are needed to recover a single\nlost bit of the encoding. In particular, we show that if the code-rate is\n\ε less than the capacity, then for optimal codes, the maximum number\nof codeword symbols required to recover one lost symbol must scale as\n\log1/\ε.\n Several variations on---and extensions of---these results are also developed.\n