利用图的完全1-因子分解构造双容错数据布局  

Construct Double-Erasure-Correcting Data Layout Using P1F

作　　者：王刚[1] 董沙莎[1] 刘晓光[1] 林胜[1] 刘璟[1] 

机构地区：[1]南开大学信息技术科学学院计算机系,天津300071

出　　处：《电子学报》2006年第B12期2447-2450,共4页Acta Electronica Sinica

基　　金：国家自然科学基金(No.906120001);天津市科技发展计划重点项目(No.043800311;No.04315111-14)

摘　　要：本文介绍了一种full-2码的虚拟顶点简单图表示法,简化了双容错数据布局判定定理,最优冗余数据布局定理和双容错数据布局的构造.本文还提出了一种基于完全二部图(对应二维奇偶校验码)的完全1-因子分解的双容错数据布局构造方法,可构造高扩展性双容错数据布局BG-HEDP.与B-CODE等同类双容错数据布局相比,BG-HEDP同样具有更新代价最优、高可靠性和低编码/解码复杂度的优点,冗余率接近最优,而扩展性更好.We present a ＂virtual node＂ simple graph representation for full-2 code （corresponds to complete graph）, this representation simplifies the double-erasure-correcting data layout judgment theorem, the optimal redundancy data layout theorem and the construction of B-CODE.We also present a data layout construction method based on PIF of complete bipartite graph （corresponds to 2d parity code）, this method can produce highly extensible double-erasure-correcting data layouts （BG-HEDP）. Compared with other data layouts, such as B-CODE, BG-HEDP also has optimal update penalty, high reliability and low encoding/decoding complexity,its redundancy is very close to optimal value, while it is superior in extensibility to others.

关 键 词：磁盘阵列 双容错编码 数据布局 完全二部图 完全1-因子分解 

分 类 号：TP302.8[自动化与计算机技术—计算机系统结构] TP333.3[自动化与计算机技术—计算机科学与技术]