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

IEEE International Symposium on Information Theory (ISIT)

作者： Tamo, Itzhak Wang, Zhiying Bruck, Jehoshua CALTECH Dept Elect Engn Pasadena CA 91125 USA

ISBN: (纸本)9781457705953

mds array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an mds code can correct then the rebuilding ratio is 1 (access all the remaining information). However, the interesting (and more practical) case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an mds code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between 1/2 and 3/4, however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. In general, we construct a new family of r-erasure correcting mds array codes that has optimal rebuilding ratio of 1/r in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the case r = 2 they use a finite field of size 3) and an optimal update property.

关键词： 2-erasure correcting code arrays Bandwidth Encoding Frequency modulation mds array codes Maintenance engineering Systematics error correction codes optimal rebuilding storage systems

来源：评论

学校读者我要写书评

暂无评论

New efficient mds array codes for RAID -: Part II:: Rabin-like codes for tolerating multiple (≥ 4) disk failures

引用

IEEE TRANSACTIONS ON COMPUTERS 2005年第12期54卷 1473-1483页

作者： Feng, GL Deng, RH Bao, F Shen, JC Univ Louisiana Lafayette Ctr Adv Comp Studies Lafayette LA 70504 USA Inst Informat Res Singapore Singapore

A new class of Binary Maximum Distance Separable (mds) array codes which are based on circular permutation matrices are introduced in this paper. These array codes are used for tolerating multiple ( >= 4) disk failures in Redundant arrays of Inexpensive Disks (RAID) architecture. The size of the information part is m x n, where n is the number of information disks and (m+1) is a prime integer;the size of the parity-check part is m x r, the minimum distance is r + 1, and the number of parity-check disks is r. In practical applications, m can be very large and n ranges from 20 to 50. The code rate is R= n/n+r. These codes can be used for tolerating up to r disk failures, with very fast encoding and decoding. The complexities of encoding and decoding algorithms are O(rmn) and O(m(3)r(4)), respectively. When r = 4, there need to be 9mn XOR operations for encoding and (9n+95)(m+1) XOR operations for decoding.

关键词： Rabin codes mds array codes RAID multiple disk failures

来源：评论

学校读者我要写书评

暂无评论

HVD code: a class of mds array codes for tolerating triple disk failures

引用

IET COMMUNICATIONS 2019年第6期13卷 748-757页

作者： Chen, Xin Cai, Suihua Ma, Xiao Sun Yat Sen Univ Sch Elect & Informat Technol Guangzhou Guangdong Peoples R China Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou Guangdong Peoples R China Sun Yat Sen Univ Guangdong Key Lab Informat Secur Technol Guangzhou Guangdong Peoples R China

In this study, the authors propose a class of exclusive OR (XOR)-based maximum distance separable (mds) array codes, referred to as horizontal-vertical-diagonal (HVD) codes, which can tolerate triple disk failures with optimal update complexity. The HVD code has a similar data/parity layout to the horizontal-vertical (HV) code and has many figures of merits as the HV code. Also, an efficient recovery algorithm is proposed, which can be implemented to accelerate the recovery process of double disk failures by making full use of all kinds of parities in the HVD code. The authors evaluate the encoding/decoding efficiency of the HVD code by comparing the number of XORs and the number of disk reads with other mds array codes. Results show that the HVD code inherits most of the merits of the HV code and requires less number of disk reads when recovering single disk failure.

关键词： storage management decoding fault tolerant computing disc storage RAID encoding codes HVD code mds array codes triple disk failures exclusive OR-based maximum distance separable array codes horizontal-vertical-diagonal codes horizontal-vertical code HV code double disk failures

来源：评论

学校读者我要写书评

暂无评论

New efficient mds array codes for RAID part I: Reed-Solomon-like codes for tolerating three disk failures

引用

IEEE TRANSACTIONS ON COMPUTERS 2005年第9期54卷 1071-1080页

作者： Feng, GL Deng, RH Bao, F Shen, JC Univ SW Louisiana Ctr Adv Comp Studies Lafayette LA 70504 USA Inst Informat Res Singapore Singapore ASTAR Inst Infocomm Res Singapore Singapore

This paper presents a class of binary Maximum Distance Separable (mds) array codes for tolerating disk failures in Redundant arrays of Inexpensive Disks (RAID) architecture based on circular permutation matrices. The size of the information part is m x n, the size of the parity-check part is m x 3, and the minimum distance is 4, where n is the number of information disks, the number of parity-check disks is 3, and (m + 1) is a prime integer. In practical applications, m can be very large and n is from 20 to 50. The code rate is R = n/n+3. These codes can be used for tolerating three disk failures. The encoding and decoding of the Reed-Solomon-like codes are very fast. There need to be 3mn XOR operations for encoding and (3mn + 9(m + 1)) XOR operations for decoding.

关键词： low-density-parity-check codes mds array codes RAID multiple disk failures Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

Explicit Constructions of High-Rate mds array codes With Optimal Repair Bandwidth

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第4期63卷 2001-2014页

作者： Ye, Min Barg, Alexander Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Inst Syst Res College Pk MD 20742 USA Inst Informat Transmiss Problems Moscow 127051 Russia

Maximum distance separable (mds) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an mds code with k information nodes and r = n - k parity nodes is used to encode data in a distributed storage system. It is known that if h out of the n nodes are inaccessible and d surviving (helper) nodes are used to recover the lost data, then we need to download at least h/(d + h - k) fraction of the data stored in each of the helper nodes (Dimakis et al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any h erased nodes from any d helper nodes, we say that the mds code has the (h, d)-optimal repair property. We study high-rate mds array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any r and n, we present 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. We also construct several other related families of mds codes with the optimal repair property.

关键词： Distributed storage mds array codes regenerating codes simultaneous repair universally error-resilient repair

来源：评论

学校读者我要写书评

暂无评论

Towards Practical Private Information Retrieval From mds array codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2020年第6期68卷 3415-3425页

作者： Li, Jie Karpuk, David Hollanti, Camilla Aalto Univ Dept Math & Syst Anal FI-00076 Aalto Finland Hubei Univ Hubei Key Lab Appl Math Fac Math & Stat Wuhan 430062 Peoples R China Univ Los Andes Dept Matemat Bogota 111711 Colombia F Secure Corp Helsinki 00180 Finland

Private information retrieval (PIR) is the problem of privately retrieving one out of M original files from N severs, i.e., each individual server gains no information on the identity of the file that the user is requesting. Usually, the M files are replicated or encoded by a maximum distance separable (mds) code and then stored across the N servers. Compared to mere replication, mds-coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR protocols from MSR-coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from mds array codes is proposed, subsuming PIR from MSR-coded servers as a special case. Particularly, only the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from mds-/MSR-coded servers. By choosing different mds array codes, the new PIR protocol can have varying advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-)optimal repair bandwidth, 3) implementable over the binary field F-2.

关键词： Capacity mds array codes private information retrieval (PIR) repair bandwidth sub-packetization

来源：评论

学校读者我要写书评

暂无评论

A Generic Transformation to Enable Optimal Repair/Access mds array codes With Multiple Repair Degrees

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第7期69卷 4407-4428页

作者： Liu, Yi Li, Jie Tang, Xiaohu Southwest Jiaotong Univ CSNMT Int Coop Res Ctr MoST Informat Coding & Transmiss Key Lab Sichuan Prov Chengdu 610031 Peoples R China Hubei Univ Fac Math & Stat Hubei Key Lab Appl Math Wuhan 430062 Peoples R China

In the literature, most of the known high-rate (n, k) mds array codes with the optimal repair property only support a single repair degree (i.e., the number of helper nodes contacted during a repair process) d, where k = d = n - 1. However, in practical storage systems, the number of available nodes changes frequently. Thus, it is preferred to construct (n, k) mds array codes with multiple repair degrees and the optimal repair property for all nodes. To the best of our knowledge, only two high-rate mds array codes have such properties in the literature, which were proposed by Ye and Barg (IEEE Trans. Inform. Theory, 63(10), 2001-2014, 2017). However, their sub-packetization levels are relatively large. In this paper, we present a generic construction method that can convert some mds array codes with a single repair degree into ones with multiple repair degrees and optimal repair property for a set of nodes, while the repair efficiency/degrees of the remaining nodes can be kept. As an application of the generic construction method, an explicit construction of high-rate mds array code with multiple repair degrees and the optimal access property for all nodes is obtained over a small finite field by choosing the code proposed by Vajha et al. as the base code. Especially, the sub-packetization level is much smaller than that of the two codes proposed by Ye and Barg concerning the same parameters n and k.

关键词： Distributed storage high-rate mds array codes sub-packetization optimal repair repair degree

来源：评论

学校读者我要写书评

暂无评论

New Constructions of mds array codes and Optimal Locally Repairable array codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第3期70卷 1806-1822页

作者： Fang, Weijun Lv, Jingjie Chen, Bin Xia, Shu-Tao Chen, Xiangyu Shandong Univ Key Lab Cryptol Technol & Informat Secur Minist Educ Qingdao 266237 Peoples R China Quancheng Lab Jinan 250103 Peoples R China Tsinghua Univ Tsinghua Shenzhen Int Grad Sch Shenzhen 518055 Peoples R China Harbin Inst Technol Dept Comp Sci & Technol Shenzhen 518055 Peoples R China Huawei Technol Co Ltd Shenzhen 518055 Peoples R China

mds array codes have been extensively studied due to their applications in storage systems. In this paper, we first propose a novel method of constructing mds array codes by deleting one row and one column from the circulant matrices associated to some polynomials. Several new classes of mds array codes with flexible parameters are constructed. In particular, we give a new algebraic presentation of the Blaum-Roth codes with sparser parity-check matrices. We also obtain a family of mds array codes over finite fields with even characteristics whose parity-check matrices have the lowest density. Furthermore, based on these new mds array codes, we give a general construction of optimal locally repairable array codes (LRACs) achieving the Singleton-type bound. Additionally, we obtain some new optimal LRACs of long lengths. Finally, we present a scheduled algorithm for syndrome computations of binary optimal LRACs with redundancy 4, which can tolerate three failures. The number of XORs per data bit required in our algorithm approaches 2 as the length approaches infinity, which is the same as the mds codes tolerating three failures. However, the number of nodes required during the repair of a failed node in our optimal LRACs is only about half of that in mds array codes.

关键词： mds array codes locally repairable array codes circulant matrices Blaum-Roth codes syndrome computation

来源：评论

学校读者我要写书评

暂无评论

A Generic Transformation to Generate mds array codes With δ-Optimal Access Property

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2022年第2期70卷 759-768页

作者： Liu, Yi Li, Jie Tang, Xiaohu Southwest Jiaotong Univ CSNMT Int Coop Res Ctr MoST Informat Coding & Transmiss Key Lab Sichuan Prov Chengdu 610031 Peoples R China Huawei Tech Investment Co Ltd Theory Lab Hong Kong Peoples R China

Recently, some high-rate maximum distance separable (mds) array codes were designed to optimally repair a single failed node by connecting all the surviving nodes. However, in practical systems, sometimes not all the surviving nodes are available. To facilitate the practical storage system, a few constructions of (n,k) mds array codes with the property that any single failed node can be optimally repaired by accessing any d surviving nodes (i.e., minimum-storage regenerating (MSR) codes) have been proposed, where d is an element of [k + 1: n - 1). However, all high-rate mds array codes with this property either have large sub-packetization levels or are not explicit for all the parameters. To address these issues, we propose a generic transformation that can convert any (n',k') mds array/scalar code to another (n = n' - delta, k = k' - delta) mds array code with the optimal repair property and optimal access property for an arbitrary set of two nodes, while the repair efficiency of the remaining n - 2 nodes can be kept, where 2 <= delta <= n' - k'. By recursively applying the generic transformation to an mds scalar code multiple times, we get a high-rate mds array code with the optimal repair property and the optimal access property for all nodes, which outperforms previous known high-rate mds array codes in terms of either the sub-packetization level or the flexibility of the parameters.

关键词： codes Maintenance engineering Peer-to-peer computing Bandwidth Galois fields arrays Codecs Distributed storage high-rate MSR codes mds array codes sub-packetization optimal repair optimal access

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：