检索结果-内蒙古大学图书馆

mds array codes with efficient repair and small sub-packetization level

DESIGNS codeS AND CRYPTOGRAPHY 2024年第11期92卷 3783-3798页

作者： Li, Lei Yu, Xinchun Ying, Chenhao Chen, Liang Dong, Yuanyuan Luo, Yuan Shanghai Jiao Tong Univ Dept Comp Sci & Engn Dongchuan Rd 800 Shanghai 200240 Peoples R China Tsinghua Univ Inst Data & Informat Shenzhen Int Grad Sch Lishui Rd Shenzhen 518055 Guangdong Peoples R China Alibaba Grp West Wenyi Rd Hangzhou Zhejiang Peoples R China

Modern data centers use erasure codes to provide high storage efficiency and fault tolerance. Reed-Solomon code is commonly deployed in large-scale distributed storage systems due to its ease of implementation, but it consumes massive bandwidth during node repair. Minimum storage regenerating (MSR) codes is a class of maximum distance separable (mds) codes that achieve the lower bound on repair bandwidth. However, an exponential sub-packetization level is inevitable for MSR codes, resulting in massive disk I/O consumption during node repair. Disk I/O is becoming the bottleneck of the performance in data centers where the storage system needs to frequently provide high-speed data access to clients. In this paper, we consider disk I/O as an important metric to evaluate the performance of a code and construct mds array codes with efficient repair under small sub-packetization level. Specifically, two explicit families of mds codes with efficient repair are proposed at the sub-packetization level of O(r), where r denotes the number of parities. The first family of codes are constructed over a finite field F-q(m) where q >= n is a prime power, m>r(l-1)+1, n and l denote the code length and sub-packetization level, respectively. The second family of codes are built upon a special binary polynomial ring where the computation operations during node repair and file reconstruction are only XORs and cyclic shifts, avoiding complex multiplications and divisions over large finite fields.

关键词： Distributed storage system mds array code Sub-packetization level Repair bandwidth

来源：评论

学校读者我要写书评

暂无评论

Constructing mds array codes with Small Repair Bandwidth under Sub-packetization Two 15

Constructing MDS Array Codes with Small Repair Bandwidth und...

引用

15th IEEE International Conference on Wireless Communications and Signal Processing, WCSP 2023

作者： Li, Lei Ying, Chenhao Yu, Xinchun Chen, Liang Dong, Yuanyuan Luo, Yuan Shanghai Jiao Tong University Department of Computer Science and Engineering Shanghai200240 China Shenzhen International Graduate School of Tsinghua University Institute of Data and Informtion Shenzhen518055 China Alibaba Group Hangzhou310030 China

ISBN: (纸本)9798350324662

Erasure codes are widely implemented in distributed storage systems to achieve fault tolerance with high storage efficiency. Reed-Solomon code is commonly deployed in data centers due to its optimal storage efficiency, but it requires massive repair bandwidth for node repair. Minimum Storage Regenerating (MSR) code and Locally Repairable (LR) code are proposed to reduce repair bandwidth. However, MSR code usually carries a heavy disk I/O burden and LR code is not optimal in storage efficiency. In this paper, we take disk I/O, storage efficiency, repair bandwidth, sub-packetization level, and repair degree (number of helper nodes) into consideration together, and propose explicit construction of mds array code (named LDIO code) with low disk I/O and reduced repair bandwidth, where the sub-packetization level is 2. Besides the low disk I/O consumption, LDIO code also achieves a small repair bandwidth of γ = 12 + 14(r - 1) for systematic nodes with repair degree d = k+1. Normally, LDIO code can provide bandwidth savings of 25% to 50% for the repair of systematic nodes compared with RS code, and almost savings of 6% compared with piggybacking code. For an LDIO code of length n and redundancy r, the size of the finite field needed is Θ(nr+1). © 2023 IEEE.

关键词： disk I/O Distributed storage system mds array code repair bandwidth small sub-packetization level

来源：评论

学校读者我要写书评

暂无评论

Building Capacity-Achieving T-PIR Schemes for Some Parameters Over Binary Field via Subfield Sub-codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2022年第1期70卷 59-70页

作者： Xu, Jingke Wang, Libo Shandong Agr Univ Sch Informat Sci & Engn Tai An 271018 Shandong Peoples R China Jinan Univ Coll Informat Sci & Technol Guangzhou 510632 Peoples R China

The T-Private Information Retrieval (T-PIR) problem is that a user wishes to retrieve a single record from N servers, without revealing the identity of the desired record even if the number of colluding servers up to T. Here every server stores all M records and each record can be viewed as a vector over the q-ary finite field F-q. To reduce the field size, a capacity-achieving T-PIR scheme based on some mds array codes for all possible N > T, M >= 2 was constructed by Xu and Zhang in 2019. A key idea in that scheme is to construct some mds array codes in query phase, whose generator matrices satisfy the recovery property (see (C1) in Example 1, page 6), i.e., there exist some specific columns in each generator matrix such that the number of them is equal to the rank of such matrix. We call the set of each column index of those columns in each generator matrix as the column index set. However, that scheme didn't give an explicit selection of the column index set satisfying the recovery property. In this paper, let N = d(2t - 1), N > T = dt > 1, M >= 3 and d >= 1, under the constraint of 2(t-1) >= N, we present a novel method to construct capacity-achieving T-PIR schemes over the binary field with an explicit selection of the column index set. Moreover, our scheme has sub-packetization N(2t - 1)(M-2), which is optimal for all linear capacity-achieving T-PIR schemes determined by Zhang and Xu in 2019. The key to our method is that all locators and column multipliers are precisely selected such that a Generalized Reed-Solomon (GRS) code defined by them has a zero-dimensional subfield sub-code. Compared with all the known capacity-achieving T-PIR schemes for the same non-trivial parameters, ours is the first explicit capacity-achieving T-PIR scheme over the binary field.

关键词： T-private information retrieval mds array code column index set subfield sub-code

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：