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

Modified low-density mds array codes for tolerating double disk failures in disk arrays

IEEE TRANSACTIONS ON COMPUTERS 2007年第4期56卷 563-566页

作者： Fujita, Hachiro Sakaniwa, Kohichi Univ Tokyo Superrobust Computat Project Kashiwa Chiba 2778561 Japan Tokyo Inst Technol Grad Sch Sci & Engn Dept Commun & Integrated Syst Meguro Ku Tokyo 1528552 Japan

In this paper, we present a new class of low-density mds array codes for tolerating double disk failures in disk arrays. The proposed mds array code has lower encoding and decoding complexity than the EVENODD code of ... 详细信息

关键词： mds array codes RAID double disk failures

来源：评论

学校读者我要写书评

暂无评论

Candidate mds array codes for Tolerating Three Disk Failures in RAID-7 Architectures 17

Candidate MDS Array Codes for Tolerating Three Disk Failures...

引用

10th International Conference on Utility and Cloud Computing (UCC) / 4th International Conference on Big Data Computing, Applications and Technologies (BDCAT)

作者： Punekar, Mayur Malluhi, Qutaibah Wang, Yongge Desmedt, Yvo Qatar Univ Dept Comp Sci & Engn Doha Qatar UNC Charlotte Dept SIS Charlotte NC USA Univ Texas Dallas Richardson TX 75083 USA

ISBN: (纸本)9781450355490

Current storage systems use RAID-5 and RAID-6 architectures to provide protection against one and two disk failures, respectively. However, as the size of storage system grows rapidly three concurrent disk failures are becoming more frequent. To cope up with three disk failure, we propose a new RAID level, i.e., RAID-7, for which three-column-erasure tolerating mds array codes are needed. However, it is an open question as to which mds array codes should be used for RAID-7. In this paper, we compare different array codes, which can be used in RAID-7 systems that require storage efficiency (the ratio of number of information symbols to encoding (or codeword) symbols) <= 0.5. The paper discusses three column-erasure tolerating mds array codes proposed in the literature namely, [5,2] 2 x 5 BP-XOR code, [6,3] 4 x 6 lowest-density array code, [6,3] 2x6 STAR code, [6, 3] 4x6 generalized RDP code. The paper introduces a new three-column-erasure tolerating [6,3] 2 x 6 almost BP-XOR codes. We analyze annual failure rate, storage efficiency, worst case normalized encoding/update/repairing/read complexity, repair bandwidth, and number of buffers required for these codes. We also provide experimental results to understand the average case encoding and repairing complexity of BP-XOR, STAR, GRDP, and almost BP-XOR codes by implementing them in software. From our analysis and experimental results, we conclude that [6,3] 2 x 6 almost BP-XOR are best suited for RAID-7 systems with storage efficiency <= 0.5.

关键词： RAID-7 mds array codes Three-Column-Erasure Tolerating codes

来源：评论

学校读者我要写书评

暂无评论

New constructions of binary mds array codes and locally repairable array codes

New constructions of binary MDS array codes and locally repa...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Lv, Jingjie Fang, Weijun Chen, Bin Xia, Shu-Tao Chen, Xiangyu Tsinghua Univ Tsinghua Shenzhen Int Grad Sch Shenzhen 518055 Peoples R China Shandong Univ Sch Cyber Sci & Technol Qingdao 266237 Shandong Peoples R China Harbin Inst Technol Dept Comp Sci & Technol Shenzhen 518055 Guangdong Peoples R China HUAWEI Technol Co Ltd Shenzhen 518055 Guangdong Peoples R China

ISBN: (纸本)9781665421607;9781665421591

In this paper, we firstly present a new construction of binary maximum distance separable (mds) array codes, from which some types of new mds array codes of minimum distance 4 with array dimension (p-1)x(l+2) can be deduced. Based on the construction, binary locally repairable array codes (LRACs) of minimum distance 4 are also explored, whose array dimension is (p-1)x2l and column locality is l-1. Particularly, when 2 is a primitive root module p, a scheduled algorithm for syndrome computation of the LRACs is proposed, which converges to 2 XORs per data bit when l approaches infinity.

关键词： mds array codes locally repairable codes quasi-cyclic codes syndrome computation

来源：评论

学校读者我要写书评

暂无评论

Piggybacking+ codes: mds array codes with Linear Sub- Packetization to Achieve Lower Repair Bandwidth

Piggybacking+ Codes: MDS Array Codes with Linear Sub- Packet...

引用

2023 IEEE Global Communications Conference, GLOBECOM 2023

作者： Shi, Hao Jiang, Zhengyi Huang, Zhongyi Bai, Bo Zhang, Gong Hou, Hanxu Tsinghua University Department of Mathematics Sciences Beijing China Central Research Institute Huawei Tech. Co. Ltd. Theory Lab 2012 Labs Hong Kong

ISBN: (纸本)9798350310900

Piggybacking codes are a class of maximum distance separable (mds) array codes that can achieve repair bandwidth reduction of single-node failure by adding some piggyback functions in a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols of which the piggyback function can be added should be strictly less than a value in order to maintain the mds property. In this paper, we present a new class of mds array codes, call piggybacking+ codes with linear sub-packetization level and small finite field that can achieve lower repair bandwidth compared with the existing piggybacking codes. We show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction of the existing piggybacking codes for the evaluated high -code- rate parameters. Our main idea is that we design piggyback functions for data node repair and transformation functions for parity node repair such that the number of parity symbols which can add piggyback function or transformation function is larger than that of the existing piggybacking codes. © 2023 IEEE.

关键词： mds array codes Piggybacking codes repair bandwidth sub-packetization

来源：评论

学校读者我要写书评

暂无评论

A new repair-efficient piggybacking design for systematic nodes

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2025年第2期17卷 377-396页

作者： Lin, Xing Southwest Jiaotong Univ CSNMT Int Coop Res Ctr MoST Informat Coding & Transmiss Key Lab Sichuan Prov Chengdu 611756 Peoples R China

Due to the advantage of providing maximum data reliability at a given storage cost, (k+r,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k+r,k)$$\end{document} maximum distance separable (mds) array codes, in which all data symbols can be obtained by any k of k+r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k+r$$\end{document} nodes, are extensively used in distributed storage systems. (k+r,k,alpha)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k+r,k,\alpha )$$\end{document} piggybacking codes, which are a particular kind of (k+r,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k+r,k)$$\end{document} mds array codes, reaches low repair bandwidth for a failed single node and possesses small sub-packetization level alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}. In this paper, by dividing the table formed by some instances of base mds code into regions and carefully adding the data symbols in some regions as piggybacks to the parity symbols in some other regions, we design a new piggybacking code which has higher repair efficiency than t

关键词： Distributed storage systems mds array codes Piggybacking codes Systematic node repair

来源：评论

学校读者我要写书评

暂无评论

Constructing MSR codes With Subpacketization 2^n/3 for k+1 Helper Nodes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第6期69卷 3775-3792页

作者： Wang, Ningning Li, Guodong Hu, Sihuang Ye, Min Shandong Univ Key Lab Cryptol Technol & Informat Secur Minist Educ Qingdao 266237 Shandong Peoples R China Shandong Univ Sch Cyber Sci & Technol Qingdao 266237 Shandong Peoples R China Tsinghua Shenzhen Int Grad Sch Tsinghua Berkeley Shenzhen Inst Shenzhen 518055 Peoples R China

Wang et al. (IEEE Transactions on Information Theory, vol. 62, no. 8, 2016) proposed an explicit construction of an (n = k+ 2, k) Minimum Storage Regenerating (MSR) code with 2 parity nodes and subpacketization 2(k/3). The number of helper nodes for this code is d = k+ 1 = n- 1, and this code has the smallest subpacketization among all the existing explicit constructions of MSR codes with the same n, k and d. In this paper, we present a new construction of MSR codes for a wider range of parameters. More precisely, we still fix d = k + 1, but we allow the code length n to be any integer satisfying n >= k + 2. The field size of our code is linear in n, and the subpacketization of our code is 2(n/3). This value is slightly larger than the subpacketization of the construction by Wang et al. because their code construction only guarantees optimal repair for all the systematic nodes while our code construction guarantees optimal repair for all nodes.

关键词： Distributed storage repair bandwidth mds array codes minimum storage regenerating (MSR) codes sub-packetization

来源：评论

学校读者我要写书评

暂无评论

A New Construction and an Efficient Decoding Method for Rabin-Like codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2018年第2期66卷 521-533页

作者： Hou, Hanxu Han, Yunghsiang S. Dongguan Univ Technol Sch Elect Engn & Intelligentizat Dongguan 523808 Peoples R China Peking Univ Shenzhen Grad Sch Shenzhen Key Lab Informat Theory & Future Interne Shenzhen 523808 Peoples R China Peking Univ Shenzhen Grad Sch Future Network PKU Lab Natl Major Res Infrastruct Shenzhen 523808 Peoples R China

array codes have been widely used in communication and storage systems. To reduce computational complexity, one important property of the array codes is that only exclusive OR operations are used in the encoding and decoding processes. Cauchy Reed-Solomon codes, Rabin-like codes, and circulant Cauchy codes are existing Cauchy maximum-distance separable (mds) array codes that employ Cauchy matrices over finite fields, circular permutation matrices, and circulant Cauchy matrices, respectively. All these codes can correct any number of failures;however, a critical drawback of existing codes is the high decoding complexity. In this paper, we propose a new construction of Rabin-like codes based on a quotient ring with a cyclic structure. The newly constructed Rabin-like codes have more supported parameters (prime p is extended to an odd number), such that the world sizes of them are more flexible than the existing Cauchy mds array codes. An efficient decoding method using LU factorization of the Cauchy matrix can be applied to the newly constructed Rabin-like codes. It is shown that the decoding complexity of the proposed approach is less than that of existing Cauchy mds array codes. Hence, the Rabin-like codes based on the new construction are attractive to distributed storage systems.

关键词： mds array codes Rabin-like codes decoding storage systems

来源：评论

学校读者我要写书评

暂无评论

On encoding symbol degrees of array BP-XOR codes

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2016年第1期8卷 19-32页

作者： Paterson, Maura B. Stinson, Douglas R. Wang, Yongge Birkbeck Univ London Dept Econ Math & Stat Malet St London WC1E 7HX England Univ Waterloo David R Cheriton Sch Comp Sci 200 Univ Ave W Waterloo ON N2L 3G1 Canada UNC Charlotte Dept Software & Informat Syst Charlotte NC 28223 USA

Low density parity check (LDPC) codes, LT codes and digital fountain techniques have received significant attention from both academics and industry in the past few years. By employing the underlying ideas of efficient Belief Propagation (BP) decoding process (also called iterative message passing decoding process) on binary erasure channels (BEC) in LDPC codes, Wang has recently introduced the concept of array BP-XOR codes and showed the necessary and sufficient conditions for mds [k + 2, k] and [n, 2] array BP-XOR codes. In this paper, we analyze the encoding symbol degree requirements for array BP-XOR codes and present new necessary conditions for array BP-XOR codes. These new necessary conditions are used as a guideline for constructing several array BP-XOR codes and for presenting a complete characterization (necessary and sufficient conditions) of degree two array BP-XOR codes and for designing new edge-colored graphs. Meanwhile, these new necessary conditions are used to show that the codes by Feng, Deng, Bao, and Shen in IEEE Transactions on Computers are incorrect.

关键词： array codes Encoding symble degrees mds array codes Bounds on codes Error corecting codes

来源：评论

学校读者我要写书评

暂无评论

Explicit Constructions of Optimal-Access mds codes With Nearly Optimal Sub-Packetization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第10期63卷 6307-6317页

作者： Ye, Min Barg, Alexander Univ Maryland Dept ECE College Pk MD 20742 USA Univ Maryland ISR College Pk MD 20742 USA

An (n, k, l) maximum distance separable (mds) array code of length n, dimension k = n -r, and subpacketization l is formed of l x n matrices over a finite field F, with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node (recovery of one erased column) can be performed by accessing a set of d <= n -1 surviving (helper) nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimalaccess mds codes with d = n-1, the sub-packetization l satisfies the bound l >= r((k-1))/r. In our previous work (IEEE Trans. Inf. Theory, vol. 63, no. 4, 2017), for any n and r, we presented an explicit construction of optimal-access mds codes with subpacketization l = r(n-1). In this paper, we take up the question of reducing the sub-packetization value l to make it to approach the lower bound. We construct an explicit family of optimal-access codes with l = r(left perpenticularn/rright perpendicular), which differs from the optimal value by at most a factor of r2. These codes can be constructed over any finite field F as long as vertical bar F vertical bar >= r(left perpendicularn/rright perpendicular), and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), which we call group repair with optimal access. In this variation, we assume that the set of n = sm nodes is partitioned into m repair groups of size s, and require that the amount of accessed data for repair is the smallest possible whenever the d = s + k -1 helper nodes include all the other s-1 nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field F of size

关键词： Distributed storage mds array codes minimum storage regenerating codes optimal access optimal subpacketization

来源：评论

学校读者我要写书评

暂无评论

MSR codes With Linear Field Size and Smallest Sub-Packetization for Any Number of Helper Nodes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第11期70卷 7790-7806页

作者： Li, Guodong Wang, Ningning Hu, Sihuang Ye, Min Shandong Univ Key Lab Cryptol Technol & Informat Secur Minist Educ Qingdao 266237 Shandong Peoples R China Shandong Univ Sch Cyber Sci & Technol Qingdao 266237 Shandong Peoples R China Quan Cheng Lab Jinan 250103 Peoples R China IonQ Bothell WA 98021 USA

An (n, k, l) array code has k information coordinates and r = n - k parity coordinates, where each coordinate is a vector in Fl(q) for some finite field Fq. An (n, k, l) mds array code has the additional property that any k out of n coordinates suffice to recover the whole codeword. Dimakis et al. considered the problem of repairing the erasure of a single coordinate and proved a lower bound on the amount of data transmission that is needed for the repair. A minimum storage regenerating (MSR) code with repair degree d is an mds array code that achieves this lower bound for the repair of any single erased coordinate from any d out of n-1 remaining coordinates. An MSR code has the optimal access property if the amount of accessed data is the same as the amount of transmitted data in the repair procedure. The sub-packetization l and the field size q are of paramount importance in MSR code constructions. For optimal-access MSR codes, Balaji et al. proved that l >= s(n/s) , where s = d - k + 1. Rawat et al. showed that this lower bound is attainable for all admissible values of d when the field size is exponential in n. After that, tremendous efforts have been devoted to reducing the field size. However, so far, reduction to a linear field size is only available for d is an element of {k + 1, k + 2, k + 3} and d = n - 1. In this paper, we construct the first class of explicit optimal-access MSR codes with the smallest sub-packetization l = s(n/s) for all d between k + 1 and n - 1, resolving an open problem in the survey (Ramkumar et al., Foundations and Trends in Communications and Information Theory: Vol. 19: No. 4). We further propose another class of explicit MSR code constructions (not optimal-access) with an even smaller sub-packetization s(n/(s+1)) for all admissible values of d, making significant progress on another open problem in the survey. Previously, MSR codes with l = s(n/(s+1)) and q = O(n) were only known for d = k + 1 and d = n - 1. The key insight that

关键词： mds array codes regenerating codes MSR codes cut-set bound sub-packetization level

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：