计算分布式网络中系统故障的概率

Question

我试图建立一个分布式文件系统中文件可用性的数学模型.我在MathOverflow上发布了这个问题,但这可能也被归类为CS问题,所以我也在这里给它一个镜头.

系统的工作方式如下:节点在r*b遥控节点存储文件(使用擦除代码编码),其中r是复制因子,b是整数常量.如果远程节点中至少有b个可用并且返回其文件的一部分,则擦除编码文件具有可以恢复文件的属性.

最简单的方法是假设所有远程节点彼此独立并具有相同的可用性p.根据这些假设,文件的可用性遵循二项分布,即二项分布http://bit.ly/dyJwwE

不幸的是,这两个假设可能会引入一个不容错误的错误,如本文所示:http://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf .

克服所有节点具有相同可用性的假设的一种方法是计算可用/不可用节点的每种可能组合的概率,并取所有这些结果的总和(这是他们在上面的论文中建议的那种,比我刚才描述的更正式.您可以将此方法视为具有深度r*b的二叉树,并且每个离开是可用/不可用节点的一种可能组合.文件的可用性与您通过> = b可用节点到达的可能性相同.这种方法更正确但是具有Ordo http://bit.ly/cEZcAP的计算成本.此外,它不涉及节点独立性的假设.

你们有没有一个好的近似的想法,它引入的误差比二项式分布 - aproximation少,但计算成本比http://bit.ly/d52MM9 http://bit.ly/cEZcAP好？

您可以假设每个节点的可用性数据是由一组元组组成的(measurement-date, node measuring, node being measured, succes/failure-bit).使用此数据,您可以计算节点之间可用性与可用性差异的相关性.

Answer 1

对于大型r和b您可以使用一个名为蒙特卡洛积分方法,例如参见维基百科蒙特卡罗积分(和/或SICP的3.1.2章)来计算的总和.对于小的r和b显着不同的节点故障概率p[i],确切的方法是优越的.小到大的确切定义将取决于几个因素,最好通过实验进行尝试.

具体的示例代码:这是一个非常基本的示例代码(在Python中),用于演示这样的过程如何工作:

def montecarlo(p, rb, N):
    """Corresponds to the binomial coefficient formula."""
    import random
    succ = 0

    # Run N samples
    for i in xrange(N):
        # Generate a single test case
        alivenum = 0
        for j in xrange(rb):
            if random.random()<p: alivenum += 1
        # If the test case succeeds, increase succ
        if alivenum >= b: succ += 1
    # The final result is the number of successful cases/number of total cases
    # (I.e., a probability between 0 and 1)
    return float(succ)/N

该函数对应于二项式测试用例并运行N测试,检查b节点外的r*b节点是否存在且存在失败概率p.一些实验将说服您N在获得任何合理结果之前需要数千个样本的值,但原则上复杂性是O(N*r*b).结果的准确性可以缩放sqrt(N),即将精度提高两倍,需要增加N四倍.如果足够大,r*b这种方法将明显优越.

扩展近似:你显然需要设计测试用例,它尊重系统的所有属性.您已经建议了一些扩展,其中一些扩展可以轻松实现,而其他扩展则无法实现.让我给你几点建议:

1)在不同的,但不相关的情况下p[i],上面的代码的变化是最小的:在功能头部传递的阵列而不是单个浮子p和更换线if random.random()<p: alivenum += 1通过

if random.random()<p[j]: alivenum += 1

2)在相关的情况下,p[i]您需要有关系统的其他信息.我在评论中提到的情况可能是这样的网络:

A--B--C
   |  |
   D  E
   |
   F--G--H
      |
      J

在这种情况下A可能是"根节点"和节点的故障D可能意味着与节点的概率为100%自动故障F,G,H和J; 而节点的故障F会自动减低G,H并J等至少这是我指的是在我的评论(这是一个合理的解释,因为你谈论的概率在原来的问题的树形结构)的情况.在这种情况下,您需要修改p引用树结构的代码并for j in ...遍历树,一旦测试失败,就从当前节点跳过下层分支.当然,结果测试仍然alivenum >= b如此.

3)如果网络是无法用树结构表示的循环图,则此方法将失败.在这种情况下,您需要首先创建死或活的图节点,然后在图上运行路由算法以计算唯一的可达节点的数量.这不会增加算法的时间复杂度,但显然会增加代码的复杂性.

4)时间依赖性是不平凡的,但可能的修改,如果你知道MTBF/R(平均次无故障工作/修理),因为这可以给你的概率p通过树结构或不相关的线性的p[i]由指数之和.然后,您必须在不同的时间运行MC程序,并获得相应的结果p.

5)如果您只有日志文件(如上一段所示),则需要对该方法进行实质性修改,这超出了我在该板上的功能.日志文件需要足够彻底,以允许重建网络图的模型(以及图形p)以及所有节点的各个值p.否则,准确性将是不可靠的.这些日志文件还需要比故障和修复的时间尺度长得多,这些假设在现实生活中可能并不现实.