Ye, Barg win IEEE Data Storage Best Paper Award

The IEEE Communications Society's Data Storage Technical Committee has awarded the 2016-2017 IEEE Data Storage Best Paper Award to alumnus Min Ye (EE Ph.D. 2017) and Professor Alexander Barg (ECE/ISR) for their paper, “Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth.” This paper was published in IEEE Transactions on Information Theory, vol. 63, no. 4, April 2017, pages 2001-2014. It originally was a chapter in Ye’s Ph.D. thesis.

Min Ye is currently a postdoctoral researcher in the Department of Electrical Engineering at Princeton University, where he works for Professor Emmanual Abbe. His research interests are in coding theory, learning, information theory and statistical estimation.

About the paper
Distributed storage systems, such as those run by Google and Facebook, are widely used for data storage, with applications ranging from social networks to file and video sharing. Currently deployed systems are formed of thousands of individual drives (nodes), and drive failures occur on a daily basis. For this reason, companies utilizing or providing distributed storage solutions have increasingly turned to error-correcting coding for efficient recovery of data stored in the system.

The coding method of choice used for data protection relies on maximum distance separable (MDS) codes which provide the maximum failure tolerance for a given amount of storage overhead. The distributed nature of the system introduces new challenges in the code design that are related to the need to communicate data between the nodes during the repair of node failures. Efficient operation of the system requires minimizing the repair bandwidth, i.e., the amount of data that needs to be downloaded to repair the contents of the failed node(s). Therefore, recent research on MDS codes for distributed storage has focused on codes with optimal repair bandwidth.

In this paper, Ye and Barg present, given any r and n, two explicit constructions of MDS array codes with the (h, d)-optimal repair property for all h r and k d n - h simultaneously. Codes in the first family can be constructed over any base field F as long as |F| ≥ sn, where s = lcm(1, 2, . .. , r). The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field F as long as |F| ≥ n+1. Moreover, both code families have the optimal error resilience capability when repairing failed nodes. They also construct several other related families of MDS codes with the optimal repair property.

Published April 1, 2019