3

在基于 gossip 的协议中，我们如何保证所有节点都被消息感染？

如果我们选择随机数量的节点并向这些节点发送消息，并且这些节点也这样做，则有可能某些节点不会收到消息。

虽然无法计算，但似乎很小。但是，如果系统运行了很长时间，在某些时候，一个节点会不走运，并且会被剩余。

4

3 回答 3

2

由于两个原因，这有点难以回答：

  1. 没有真正的基于八卦的协议。最多有一系列基于八卦的算法。

  2. 这些算法实际上仅在特定假设下才能保证感染。例如，如果，正如你所说，“系统运行了很长时间”，任何给定的链接在某个指数过程（很可能的情况）下永久失败，那么概率 1 某个节点将被完全隔离，并且没有协议可以克服的。

但是，IIUC，您询问的是具有以下假设的协议：

  1. 对于任何节点组V' ⊂ V，都有一个活动链接u ∈ V' → v ∈ V ∖ V'。

在此处输入图像描述

  1. 每个节点在每一步均匀地选择它的d个邻居，而不考虑它们的状态、其他节点的选择、总更新状态等。

在此处输入图像描述

在这种情况下，您提出的问题的概率为 0。

您可以将感染视为马尔可夫链，如果i个节点被感染，则系统处于状态i 。假设一些变化起源于一些s ∈ V，因此系统从状态i开始。

  • 根据属性 1.，存在从i个受感染节点到n - i 个其他节点之一的链接。

  • 根据属性 2.，选择此链接的概率至少为1 / n。这是因为其链路恰好穿过切割线的节点最多有n 个邻居，但至少有一个邻居穿过切割线。即使它的选择是完全无状态和不知情的，这也是它选择这个邻居的机会。

因此，对于j步不会发生这种情况的概率是(1 - d/n) j。使用Union Bound ，任何状态i发生这种情况的概率最多为n (1 - 1/n) j。取j = n 2，这变为ne - n；取j = n 3，这就变成了ne - n 2。等等。

（当然，gossip 算法感染发生得更快；这是最坏情况的上限。）

因此，如果系统运行足够长的时间，某个节点没有被感染的概率会降低到 0（非常快）。对于反熵八卦协议，这就足够了。正如您所怀疑的，对于其他一些协议，某些节点可能会因某些更新而丢失。

于 2015-07-04T22:39:49.640 回答
0

我们无法提供答案，因为您不了解您的问题（因此问题不明确）

  • 网络的拓扑未知，但答案取决于它
  • 算法的停止条件是什么？是停还是不停？

假设给定节点连接到所有其他节点（即拓扑），并且每个节点在收到消息时执行相同的操作。

您可以将您的问题简化为更小的子问题（这就是divide-et-impera 方法）：想象任何节点只执行一次尝试（即i = 1）。

由于任何节点完全随机选择接收者，并且由于此操作无限次完成，因此最终所有节点都将接收到消息。需要多少次迭代才能达到给定的置信度（接收消息的节点的比率/所有节点的数量）取决于您。

一旦你得到这个，包括重复的尝试就很i简单了。

于 2015-09-04T18:32:31.653 回答
0

我对你正在尝试做的事情做了一点模拟。 http://jsfiddle.net/ut78sega/

function gossip(nodes, tries, startNode, reached) {
    var stack = [startNode, tries];
    while(stack.length > 0) {
        var ttl = stack.pop();
        var n = stack.pop();
        reached[n] = 1;
        if(ttl <= 0) { continue; }
        for(var i=0; i < ttl; i++) {
            stack.push(Math.floor(Math.random() * nodes), ttl - 1);
        }
    }
    return reached;
}
  • 节点- 总节点数
  • 尝试- 随机选择的起始数量
  • startNode - 获取第一条消息的节点
  • 到达- 当前模拟到达的节点的哈希集

在递归的每一层，尝试的次数都会减少一。大约需要 9 次尝试才能 100% 覆盖 65536 (2^16) 个节点。

于 2015-09-04T18:47:15.747 回答