图因子分解的故障节点快速修复

为了提高分布式存储系统中故障节点的修复效率,提出一种新的部分重复(fractional repetition,FR)码的构造算法.该算法利用完全图的因子分解进行构造,称为CGFBFR(complete graph factorization based FR)码.该算法首先对完全图进行因子分解,分解完成以后确定完全图的因子分解个数,根据需要存储数据块的重复度来选择完全图的因子个数,将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块,然后对选中因子图的边进行标记,标记的边当做分布式数据节点进行存储.最后根据选中的因子的顶点和边生成编码矩阵,在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储.实验仿真结果显示,本文提出的一种新的部分重复码构造算法,与分布式存储系统中的里所(reed-solomon,RS)码、简单再生码(simple regenerating codes,SRC)以及最新的循环可变部分重复(variable fractional repetition,VFR)码相比,在系统修复故障节点时,能够快速地修复故障节点,有效降低了故障节点的修复带宽开销、修复局部性、修复复杂度,而且构造过程简单,同时可以灵活选择构造参数,广泛适用于分布式存储系统中.

单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2