2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.1.4 | ||
| Paper Title | Toward Optimality in Both Repair and Update via Generic MDS Code Transformation | ||
| Authors | Hanxu Hou, Dongguan University of Technology, China; Patrick P. C. Lee, The Chinese University of Hong Kong, China; Yunghsiang S. Han, Dongguan University of Technology, China | ||
| Session | M.1: Codes for Distributed Storage I | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | An $(n,k)$ maximum distance separable (MDS) code encodes $k\alpha$ data symbols into $n\alpha$ symbols that are stored in $n$ nodes with $\alpha$ symbols each, such that the $k\alpha$ data symbols can be reconstructed from any $k$ out of $n$ nodes. MDS codes achieve optimal repair access if we can repair the lost symbols of any single node by accessing $\frac{\alpha }{d-k+1}$ symbols from each of $d$ other surviving nodes, where $k+1\leq d\leq n-1$. In this paper, we propose a generic transformation for any MDS code to achieve optimal repair access for a single-node repair among $d-k+1$ nodes, while the transformed MDS codes maintain the same update bandwidth (i.e., the total amount of symbols transferred for updating the symbols of affected nodes when some data symbols are updated) as that of the underlying MDS codes. By recursively applying our transformation for existing MDS codes with the minimum update bandwidth, we can obtain multi-layer transformed MDS codes that achieve both optimal repair access for any single-node repair among all $n$ nodes and minimum update bandwidth. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
