检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

四元域上最优局部可修复码的分类

中国科学：数学 2023年第2期53卷 339-368页

作者：奚元霄孔祥粱葛根年浙江大学数学科学学院杭州310058 首都师范大学数学科学学院北京100048

近年来,为了提高分布式存储系统的容错性和可靠性,编码学家们引入了几类新的编码方案,其中局部可修复码(locally repairable codes,LRC)起到了重要的作用.对于一个线性码,若它的一个码字符号能通过其他至多r个码字符号修复,则称其具有... 详细信息

近年来,为了提高分布式存储系统的容错性和可靠性,编码学家们引入了几类新的编码方案,其中局部可修复码(locally repairable codes,LRC)起到了重要的作用.对于一个线性码,若它的一个码字符号能通过其他至多r个码字符号修复,则称其具有局部性参数r.码长为n、维数为k、局部性参数为r的LRC((n,k,r)-LRC),其极小距离d满足Singleton型界d≤n-k-[k/r]+2.自LRC被提出以来,有许多工作研究小域上达到Singleton型界的码类.本文从码的校验矩阵角度出发,利用组合设计和有限几何的工具,研究了达到Singleton型界的最优四元LRC.本文证明了在四元域上共有27类最优的LRC,并且给出了这些最优码的构造.不仅如此,利用有限几何工具,本文还引入了判断最优LRC存在的新方法.

关键词：局部可修复码组合设计有限几何大数据存储

同方期刊数据库

在线全文

学校读者我要写书评

暂无评论

局部可修复码迭代修复次数研究

局部可修复码迭代修复次数研究

作者：郭元皓西安电子科技大学

学位级别：硕士

局部可修复码(Locally Repairable Codes,LRCs)作为纠删码(Erasure Codes,ECs)的一种,当任意一码元符号发生错误时,都只需其他至多r个符号进行恢复。因为这种特性,应用在分布式存储系统中的局部可修复码拥有广阔的发展前景。当前关于修... 详细信息

局部可修复码(Locally Repairable Codes,LRCs)作为纠删码(Erasure Codes,ECs)的一种,当任意一码元符号发生错误时,都只需其他至多r个符号进行恢复。因为这种特性,应用在分布式存储系统中的局部可修复码拥有广阔的发展前景。当前关于修复多个错误的局部可修复码的研究正在逐渐增多,例如具有连续修复能力的局部可修复码,具有并行修复能力的局部可修复码和具有可用度的局部可修复码等,其中同时具有连续修复能力和可用度的局部可修复码称为(n,k,r,tavl,tseq)-精确局部可修复码(Exact Locally Repair Codes,ELRCs)。在修复多个错误时,一般将错误坐标分为若干组进行修复,所分组数就称为迭代修复次数。迭代修复次数会极大的影响多个错误的修复效率。若修复多个错误时的迭代修复次数过高,则会有过多的错误码元需要等待其他错误码元修复。而在应用了局部可修复码的分布式存储系统中,迭代修复次数过高会导致系统可用性的降低。本文主要研究了具有多个错误修复能力的局部可修复码的迭代修复次数,包括以下内容:一方面,对于(n,k,r,tavl,tseq)-ELRC,研究其使用串并修复的迭代修复次数上界。首先,使用一种基于超图的码结构表示方法,将对错误坐标集合的复杂修复过程转换为对超图中顶点和超边的消去过程。然后,给出了更紧的适用于任意(n,k,r,2,tseq)-ELRC的迭代修复次数上界,并证明了对于任意(n,k,r,2,tseq)-ELRC,都存在一错误坐标集合使该上界的等号成立。其次,给出了已有的适用于任意(n,k,r≥2,3,tseq)-ELRC的迭代修复次数上界的构造性的证明方法,并证明对于任意参数r和tseq,都存在有(n,k,r≥2,3,tseq)-ELRC以及错误坐标集合使该上界的等号成立。再次,给出了更紧的适用于任意(n,k,r=1,tavl,tseq)-ELRC的迭代修复次数上界。最后,对于给出的两更紧的迭代修复次数的上界,通过仿真模拟与现有的结果进行了对比。另一方面,研究迭代修复次数优先的修复方式。首先,分析了并行修复,连续修复,串并修复三种修复方式以及对应的局部可修复码的优劣。然后,相对于追求有较低或者给定的迭代修复次数的局部可修复码,反其道而行之,提出迭代修复次数优先的修复方式,在所有修复集中选择与错误坐标集合无交集且基数最小的修复集以降低迭代修复次数至最低。其次,对于提出的修复方式的可行性进行了分析。再次,使用模拟退火算法实现迭代修复次数优先的修复方式。最后,通过仿真模拟,对三种不同的码分别采用并行修复,串行修复,串并修复,迭代修复次数优先的修复的迭代修复次数和局部度参数进行了分析和比较。

关键词：局部可修复码迭代修复次数串并修复修复方式局部度

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

局部可修复码修复两个故障节点的平均局部性

局部可修复码修复两个故障节点的平均局部性

作者：纪玉晖西安电子科技大学

学位级别：硕士

近年来,局部可修复码(Locally Repairable Codes,LRCs)已经广泛应用于分布式存储系统(Distributed Storage System,DSS)中。通过访问其它最多r个节点来恢复单个故障节点的LRCs具有局部性r。同时恢复任意两个故障节点需要访问的平均节点... 详细信息

近年来,局部可修复码(Locally Repairable Codes,LRCs)已经广泛应用于分布式存储系统(Distributed Storage System,DSS)中。通过访问其它最多r个节点来恢复单个故障节点的LRCs具有局部性r。同时恢复任意两个故障节点需要访问的平均节点数量r2直接影响修复带宽、磁盘I/O以及两个故障的数据块的修复过程中涉及的节点数量。本文以LRCs的平均局部性r为启发,研究同时恢复任意两个故障节点需要访问的平均节点数量r2。主要研究LRCs通过协作方式来同时恢复任意两个故障节点需要访问的平均节点数量(r2)的界限以及满足界限的LRCs结构。主要创新点及研究内容如下:首先,介绍协作方式的恢复策略来计算(n,k,d)LRCs的r2,给出了一个r2的一般界限。同时在一个特定结构下(LRCs满足任意两个局部校验组(Check Group,CG)中覆盖的变量节点(Variable Node,VN)没有重合)提出r2的界限。然后,提出一种LRCs构造算法,通过算法可以构造满足界限的LRCs结构。其次,分析得出LRCs的Tanner图中的校验组由局部校验组和全局校验组两部分组成。当丢失任意两个故障节点的时候,恢复过程首先考虑局部校验组,然后再考虑全局校验组。因此,优化r2分为两步:第一步,构造最优的局部校验组;第二步,优化全局校验组。主要工作有以下三个方面:第一,严格的证明基于三类r2最优的LRCs结构下r2的界限;第二,同时得到满足对应界限的LRCs结构;第三,重点研究了具有高码率的第三类r最优的LRCs,提出一种满足r2界限的LRCs构造算法。然后,构造一个LRC的Tanner图结构,同时找到对应Tanner图的校验矩阵H。最后,详细介绍了协作策略的译码算法,译码算法可以通过LRCs的校验矩阵H来计算r2。分别计算了一些在参数(n,k,d)相同的条件下三类r最优的LRCs的r2和本文构造的LRCs的r2。通过对数据的比较,我们发现本文构造的LRCs的r2比三类r最优的LRCs的r2分别在不同程度上得到了提高。最后,比较特定结构与基于三类r最优的LRCs结构下r2的界限,发现特定结构下r2的界限更紧。

关键词：局部可修复码分布式存储系统平均局部性 Tanner图协作策略局部校验组

基于条带配对合并算法的局部可修复码冗余度转换机制

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

计算机科学 2023年第12期50卷 89-96页

作者：杜清鹏许胤龙吴思中国科学技术大学计算机科学与技术学院合肥230027

相比传统的多副本技术,纠删码是一种以高修复代价换取低存储开销的数据冗余机制。局部可修复码是一类具有低修复代价的纠删码,被广泛应用在大数据存储系统中。为了应对动态变化的工作负载和存储介质动态改变的故障率,现代存储系统需要... 详细信息

相比传统的多副本技术,纠删码是一种以高修复代价换取低存储开销的数据冗余机制。局部可修复码是一类具有低修复代价的纠删码,被广泛应用在大数据存储系统中。为了应对动态变化的工作负载和存储介质动态改变的故障率,现代存储系统需要对纠删码数据进行冗余度转换,以调节数据访问性能和可靠性。设计了一种基于条带配对合并的局部可修复码冗余度转换方法,通过选择特定位置的条带进行配对合并,实现了冗余度转换与数据布局的解耦合;进一步通过设计代价量化方法与最优化模型,降低了冗余度转换的网络通信开销。相比设计数据布局的算法,所提算法有与其近似的性能,但对数据布局无限制,可级联迭代地多次运行。实验结果表明,在两种冗余度转换设置下,所提算法均近似于理论最优值,相比随机布局的朴素算法,网络流量分别降低了27.74%和27.47%,耗时分别缩短了39.10%和22.32%。

关键词：局部可修复码冗余度转换容错存储技术网络流量优化分布式存储系统

在线全文

学校读者我要写书评

暂无评论

基于正则填充的最优局部可修复码

基于正则填充的最优局部可修复码

作者：田旺庚河北师范大学

学位级别：硕士

在大数据的时代,许多系统经常会出现磁盘故障而导致数据丢失.因此,分布式存储系统应运而生.在分布式存储系统中,局部可修复码可使一个失效的节点通过连接其他至多r((?)k)个节点来恢复缺失的数据,从而提高存储系统的修复效率.在每个修复... 详细信息

在大数据的时代,许多系统经常会出现磁盘故障而导致数据丢失.因此,分布式存储系统应运而生.在分布式存储系统中,局部可修复码可使一个失效的节点通过连接其他至多r((?)k)个节点来恢复缺失的数据,从而提高存储系统的修复效率.在每个修复集只有一个校验元且有多个互不相交的修复集的前提下,Rawat等人构造了三类最优局部可修复码.蔡晗、程民权、范翠玲、唐小虎给出了最优局部可修复码与组合结构-填充设计之间的的关系,并构造了一些具有信息(r,δ;1)-局部度的最优局部可修复码.之后,蒋静、程民权利用可分解设计和填充设计等组合结构完全解决了具有信息(3,δ;1)-局部度的最优局部可修复码.蒋静、王金玉给出了当k≤20,k(δ-1)(?)0,3(mod 4)且(k,δ-1)(?){(14,2),(18,2)}时,具有信息(4,δ;1)-局部度的最优局部可修复码.本文基于蔡晗、程民权、范翠玲、唐小虎、蒋静、王金玉等人的研究,考虑当码的生成矩阵中校验列均为部分校验列时,讨论具有信息(4,δ;1)-局部度的[n,k,δ]最优局部可修复码的存在性.本文结构组织如下.第一章主要介绍局部可修复码的相关概念以及与具有信息(r,δ;1)-局部度的最优局部可修复码相关的组合概念.第二章给出与局部可修复码相关的一些已知结果.第三章给出具有信息(4,δ;1)-局部度的最优局部可修复码的完整组合刻画,讨论对k(δ-1)模4所有情况下的区组数为「k(δ-1)/4(?)的(k,R;1)-填充的存在性,其中max(R)=4.进而得到了具有信息(4,δ;1)-局部度的最优局部可修复码的存在性.

关键词：分布式存储系统局部可修复码填充

基于Tanner图的局部可修复码的构造方法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于Tanner图的局部可修复码的构造方法

作者：王祥旭西安电子科技大学

学位级别：硕士

现如今,科技的不断进步导致了数据量的极速增长,因此,提供了更高存储效率以及数据可靠性的分布式存储系统（Distributed Storage System,DSS）得到了广泛的应用。同时,为了能够进一步优化DSS的修复效率,针对使用较少冗余实现数据存储的... 详细信息

现如今,科技的不断进步导致了数据量的极速增长,因此,提供了更高存储效率以及数据可靠性的分布式存储系统（Distributed Storage System,DSS）得到了广泛的应用。同时,为了能够进一步优化DSS的修复效率,针对使用较少冗余实现数据存储的纠删码技术进行了相关的研究。其中,由于局部可修复码（Locally Repairable Code,LRC）能通过访问错误节点所在修复集合中,至多其它r个节点即可完成修复过程的特性,使LRC码得到了大量的关注。目前对LRC码的研究已存在很多成果,大体可以分为两部分:对参数性能的研究以及构造方法的设计。其中,在参数方面,主要针对码的最小距离,修复度等性质进行分析;在构造方面,已提出了例如基于矩阵的包括生成校验矩阵、循环嵌套矩阵;基于图形的包括Tanner图、超图;基于多项式或向量空间等一系列相关的方法。本文针对LRC码的构造方法进行研究,主要创新点及研究内容如下:一方面,对基于Tanner图的相关构造方法进行学习总结,在同时考虑LRC码的平均信息修复度,平均修复度以及更新复杂度等参数的基础上,提出了一种新的构造方法,对参数进行了优化。通过分析Tanner图的特点,首先,对图中的局部校验节点部分进行设计,使码的平均信息修复度ri达到最优;其次,通过分析局部组的特点,对不同情况下的重叠组进行分类构造,从而优化码的平均修复度r;再次,通过对全局校验节点的部分进行设计,在保证最小距离的前提下,优化码的更新复杂度;最后,对构造码的算法复杂度进行了分析及对比。结果表明,在满足前提时,所提方法在优化上述参数性能的同时,降低了 LRC码在构造过程中的复杂度。另一方面,通过对具有修复能力LRC码的构造方法进行学习,对上述中的构造方法进行了扩展。在进一步考虑修复能力的前提下,同样基于Tanner图,提出了一种构造（r,t=2）iLRC的方法,并根据方法的结构设计特点,给出了相关的前提条件及解释说明,对于参数为（n,k,r）的LRC码,若满足条件即可进行构造。首先,通过对局部组的分组方法进行设计,相对降低了各个组所包含信息变量节点的数量,为下一步的构造做准备;其次,基于组合的思想,提出了针对信息变量节点构造修复能力的设计方法;最后,对所提方法的构造特点进行说明,通过对比分析并结合具体的实例,表明新提出的方法,不仅能够得到具有（r,t=2）i性质的LRC码,同时进一步扩大了具有相同性质的码字的适用范围,即在满足前提时,新提出的构造可以得到多组具有相同性质的码字结果。

关键词：局部可修复码 Tanner图修复度修复能力更新复杂度

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

循环局部可修复码的构造

循环局部可修复码的构造

作者：陈敏合肥工业大学

学位级别：硕士

局部可修复码(LRC)是一种能修复多个故障节点的纠删码,在分布式存储系统中被广泛使用,构造最优局部可修复码是目前分布式存储编码理论研究的热点问题之一。本文对有限域上循环局部可修复码的构造进行了研究,利用循环码及其定义集的结构... 详细信息

局部可修复码(LRC)是一种能修复多个故障节点的纠删码,在分布式存储系统中被广泛使用,构造最优局部可修复码是目前分布式存储编码理论研究的热点问题之一。本文对有限域上循环局部可修复码的构造进行了研究,利用循环码及其定义集的结构来刻画修复度;通过分析零点的构成,确定循环局部可修复码的最小Hamming距离。特别地,研究了有限域F上长度为n=λ(q+1)和n=λ(q-1)的循环码,构造了若干类最优循环局部可修复码。具体结果如下:(1)选取特殊的定义集,刻画循环局部可修复码中的修复度,进而研究有限域F循环(r,δ)-局部可修复码的一些性质。(2)给出了分圆陪集的结构,结合循环码的BCH界和Hartmann-Tzeng界,构造了F上长度为n=λ(q-1)和n=λ(q+1)的最优循环(r,δ)-局部可修复码。(3)通过分析循环码零点的构成,构造了两类局部修复度为r=2,3的最优循环(r,δ)-局部可修复码,它们长度都大于q-1,并且具有较大的极小Hamming距离。

关键词：局部可修复码循环码定义集分圆陪集 BCH界

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

稀疏超图:从理论到应用

中国科学：数学 2023年第2期53卷 187-216页

作者：上官冲葛根年山东大学数学与交叉科学研究中心青岛266237 首都师范大学数学科学学院北京100048

给定正整数r、e和v,如果某个r-一致超图的任意e条不同边的并都包含至少v+1个顶点,则称其是(v, e)-自由(free)或者(v, e)-稀疏的.稀疏超图的概念由Brown、Erd?s和Sós在20世纪70年代提出.目前,研究给定顶点数的稀疏超图所能包含最大边数... 详细信息

给定正整数r、e和v,如果某个r-一致超图的任意e条不同边的并都包含至少v+1个顶点,则称其是(v, e)-自由(free)或者(v, e)-稀疏的.稀疏超图的概念由Brown、Erd?s和Sós在20世纪70年代提出.目前,研究给定顶点数的稀疏超图所能包含最大边数的上下界已成为极值组合学研究领域内的核心问题之一.该问题的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.本文介绍Brown、Erd?os和S′os关于稀疏超图的两个重要猜想的最新研究进展以及稀疏超图在极值组合与信息科学中的若干应用,包括朱烈曾作出突出贡献的完美哈希(Hash)矩阵、可分哈希矩阵等几类信息安全中的研究问题.此外,本文在某些参数下给出完美哈希矩阵与求并-自由(union-free)超图的新构造.本文的构造改进了相应问题的已知最优下界.

关键词：稀疏超图 Brown-Erd?s-Sós猜想完美哈希矩阵可消去(cancellative)超图求并-自由超图集中式编码缓存组合列表译码局部可修复码

在线全文

学校读者我要写书评

暂无评论

三数据中心下的纠删码算法研究

计算机科学 2024年

作者：孙婧牛虹婷梁松涛华东政法大学智能科学与信息法学系北京航空航天大学计算机学院上海哔哩哔哩科技有限公司多媒体技术中心

纠删码算法在单数据中心和多数据中心得到了广泛的应用。目前对纠删码算法研究更多的关注在存储成本和修复带宽上，而如何在专线带宽、交换机受限的情况下完成多数据中心之间的修复；如何在可靠性、容错能力等核心因素之间做比较优的权... 详细信息

纠删码算法在单数据中心和多数据中心得到了广泛的应用。目前对纠删码算法研究更多的关注在存储成本和修复带宽上，而如何在专线带宽、交换机受限的情况下完成多数据中心之间的修复；如何在可靠性、容错能力等核心因素之间做比较优的权衡等问题，没有得到充分的分析和解决。针对三数据中心这种最常用的多数据中心场景，首先，提出了纠删码在系统设计中重要的四个因素：冗余度、可靠性、容错能力及解码带宽。其次，根据提出的四个因素，设计了一种单数据中心下满足最优带宽修复的S-LRC算法。再根据提出的S-LRC算法，设计了满足三中心架构体系下的G-LRC算法。相比传统的编码方案，提出的G-LRC算法具有更高的可靠性、更大容错性及解码带宽惩罚比。其两节点故障时解码带宽惩罚比只为传统方案的1/7～2/7。最后，还将G-LRC算法在大文件存储系统中进行了实现和验证，并且设计了解码最优决策算法来减少修复的带宽，解决了非最大距离可分割码算法在系统中落地难的问题。

关键词：三数据中心纠删码局部可修复码最大可恢复编码 Reed-Solomon码