月度归档：7月 2012

Max-flow min-cut （最大流-最小割定理）

Posted on by
2

最大流-最小割定理是网络信息流理论（Network infomation flow）的基石。这个定理我的理解就是“多粗的管子，水就最多多大流量”，比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大？考虑到可能从水厂到小区有不少到达的水管，那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨，因为这里水管不是双向的，而在网络中谈论的信息流却可是是双向的。下面详细介绍最大流—-最小割定理。

继续阅读 →

冗余编码的存储系统中最多允许多少节点失效？

Posted on by
回复

本文讨论分布式存储系统如果采用编码方式保存数据，那么允许最多失效的节点个数与码率之间的关系。这个关系也可以通过图论中“最小分割最大流”定理来求证。

一个原始文件S（假设没有冗余信息）大小自信息量/文件大小为I ，进行冗余编码[n’,k]（这里考虑系统码，为和分不到n 个节点区分开，用n’ 代替）的编码率为R = k/n’ ，则编码后文件大小为C：I → C = I/R。将编码后的数据分布在n 个节点上，每个节点的数据记做：X1 ，X2 ，X3 ……Xn ，每个节点数据的大小为C/n = I/R·n 。而每个节点数据/信息又有两部分组成，前一部分是系统码中的原始信息：Xii = I/n，另一部分是系统码中的校验信息：Xih = C/n – I/n ，且Xi = Xii + Xih。如下图所示

6_0               6

当a 个节点发生故障失效时，那么剩下的校验/冗余信息和原始信息应该能够恢复出丢失的原始信息，进而恢复出所有的校验信息。即：

    $$\frac{n-a}{n} \cdot H \geq \frac{a}{n} \cdot I$$

  因为H = C – I =I/R – I。得结果：

    $$\frac{n-a}{n} \geq R $$

这也就是说，所有没有损坏节点的个数与所有节点比率（n-a/n）应该大于编码码率R。