- 170 views
- 151 downloads
Improving the Update Complexity of Locally Repairable Linear Block Codes in Distributed Storage Systems
-
- Author / Creator
- Mehrabi, Mehrtash
-
Distributed and cloud storage systems are used to reliably store large-scale data. Erasure codes have been recently proposed and used in real-world distributed and cloud storage systems such as Google File System, Microsoft Azure Storage, and Facebook HDFS-RAID, for reliable data storage. Conventional erasure codes, however, are not suitable for distributed storage systems, as they cause significant repair bandwidth and disk I/O. As a solution, a class of erasure codes called locally repairable codes (LRCs) have been proposed. Using LRCs repairing a failed storage nodes requires access to only a small number of available nodes. This property of LRCs results in a relatively low bandwidth and disk I/O operations for repairing a failed node. In this thesis, we study update complexity of LRCs. Update complexity of an erasure code is a measure of the computation, I/O and networking costs associated with updating an information block in a distributed storage system. LRCs with low update complexities are desirable. In this thesis, we derive lower bounds on update complexity of an important class of LRCs. Then, we propose a new set of LRCs, and, using the bound, we show that our designed codes have either optimal or near-optimal update complexities. Interestingly, our proposed codes improve update complexity without sacrificing important code parameters such as minimum distance, rate, or locality.
-
- Subjects / Keywords
-
- Graduation date
- Spring 2018
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.