In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node. Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code. This survey provides an overview of the efforts in this direction that have taken place over the past decade. Citation Balaji S B, Krishnan M N, Vajha M, et al. Erasure coding for distributed storage: an overview. Sci China Inf Sci, 2018, 61(10): 100301, https://doi. Figure 1 (Color online) An overview of the different classes of codes for distributed storage discussed in this survey article. Coding theorists have responded to this need by coming up with two new classes of codes, namely regenerating (RG) and locally recoverable (LR) codes. The focus in an RG code is on minimizing the amount of data download needed to repair a failed node, termed the repair bandwidth while LR codes seek to minimize the number of helper nodes contacted for node repair, termed the repair degree. In a different direction, coding theorists have also re-examined the problem of node repair in RS codes and have come up with new and more efficient repair techniques. This survey provides an overview of these recent developments. An outline of the survey itself appears in Figure 1 . RG codes are discussed in Section 2. The two principal classes of RG codes, namely minimum bandwidth regenerating (MBR) and minimum storage regeneration (MSR) appear in the two sections that follow. These two classes of codes are at the two extreme ends of a tradeoff known as the storage-repair bandwidth (S-RB) tradeoff. A discussion on codes that correspond to the interior points of this tradeoff appears in Section 5. The theory of RG codes has been extended in several directions and these are explored in Section 6. Section 7 examines LR codes. There have been several approaches at extending the theory of LR codes to handle multiple erasures and these are dealt with in Section 8. A class of codes known as locally regenerating (LRG) codes that offer both low repair bandwidth and low repair degree within a single erasure code is discussed in Section 9. This is followed by Section 10 that discusses recent advances in the repair of RS codes. A brief description of a different approach based on capacity considerations and leading to the development of a liquid cloud storage system appears in Section 11. The final section, discusses practical evaluations and implementations. Disclaimer. This survey is presented from the perspective of the authors and is biased in this respect. Given the explosion of research activity in this area, the survey also does not claim to be comprehensive and we offer our apologies to the authors whose work has inadvertently or for lack of space, not been appropriately cited. We direct the interested reader to some of the excellent surveys of codes on distributed storage contained in the literature including [3] [4] [5] [6] .
Readers interested in an extended overview of erasure codes for distributed storage are referred to REF .
Erasure coding for distributed storage: an overview
Science China Information Sciences
Science China Information Sciences
Mathematics Computer Science