ceClub: Optimal Rebuilding in Distributed Storage Systems

Zhiying Wang (Caltech)
Wednesday, 28.11.2012, 11:30
EE Meyer Building 861

Distributed storage systems have become a popular solution to large file storage and fast data access. In such systems, erasure-correcting codes are widely used to combat disk failures, where disks correspond to symbols in the code. Specifically, we study MDS (maximum distance separable) array codes which enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In this talk we will show that the lower bound of 1/2 is achievable and that the result can be generalized to optimally rebuild an arbitrary number of parities.

Bio: Zhiying Wang received the B.Sc. degree in Information Electronics and Engineering from Tsinghua University, Beijing, China, in 2007 and M. Sc. degree in Electrical Engineering from California Institute of Technology, Pasadena, USA, in 2009. She is now a Ph.D. candidate with the department of Electrical Engineering, California Institute of Technology. Her research focuses on information theory, coding theory, with an emphasis on coding for storage devices and systems.

Back to the index of events