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

StackOverflow https://stackoverflow.com/questions/3092694

题

我正在尝试建立一个数学模型，以在分布式文件系统中构建文件的可用性。我在Mathoverflow上发布了这个问题，但这也可以归类为CS问题，因此我也在这里给它拍摄。

该系统的工作原理：A节点在r*b求遥节点上存储一个文件（使用擦除代码包含），其中r是replication-factor，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. 。同样，它不涉及节点独立性的假设。

你们对近似值的想法是否比二项式分配 - 近距离示威更少，但计算成本比 http://bit.ly/d52mm9 http://bit.ly/cezcap?

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

有帮助吗？

解决方案

大 r 和 b 您可以使用称为蒙特卡洛集成的方法，请参阅EG 蒙特卡洛在维基百科 （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. 。否则，准确性将不可靠。这些日志文件还需要大幅度的时间比故障和维修的时间尺度，这是在现实生活中可能不现实的假设。

其他提示

假设每个节点都有一个恒定，已知和独立的可用性率，则想到了鸿沟和征服方法。

说你有 N 节点。

  1. 将它们分成两组 N/2 节点。
  2. 对于每一侧，计算任何数量的节点的概率（[0,N/2]）下降。
  3. 乘以并根据需要汇总这些数字的概率（[0,N]）完整套装。

步骤2可以递归完成，在最高级别您可以根据需要查找超过某些数字的频率。

我不知道这一点的复杂性，但是如果我必须猜测，我会在或下面说 O(n^2 log n)

可以在终端情况下说明其机制。说我们有5个节点有时间 p1...p5. 。我们可以将其分成细分市场 A 和p1...p2 和 B 和 p3...p5. 。然后，我们可以处理这些段的“ n个节点”时间：

为一个：

a_2

a_1

a_0

对于B：

b_3

b_2

可以通过乘以每个阶段的最终结果 a每一个 b适当地总结。

v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] =             a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] =                         a[2]*b[2] + a[1]*b[3]
v[5] =                                     a[2]*b[3]
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top